title: Efficient Algorithm for String Concatenation with Overlap
body: <p>We need to combine 3 columns in a database by concatenation. However, the 3 columns may contain overlapping parts and the parts should not be duplicated. For example,</p>
  
  <pre><code>  "a" + "b" + "c" =&gt; "abc"
    "abcde" + "defgh" + "ghlmn" =&gt; "abcdefghlmn"
    "abcdede" + "dedefgh" + "" =&gt; "abcdedefgh"
    "abcde" + "d" + "ghlmn" =&gt; "abcdedghlmn"
    "abcdef" + "" + "defghl" =&gt; "abcdefghl"
  </code></pre>
  
  <p>Our current algorithm is pretty slow because it uses brute-force to identify the overlapping part between 2 strings. Does any one know an efficient algorithm to do this?</p>
  
  <p>Say we have 2 strings A and B. The algorithm needs to find the longest common substring S so that A ends with S and B starts with S.</p>
  
  <p>Our current brute-force implementation in Java is attached for reference,</p>
  
  <pre><code>public static String concat(String s1, String s2) {
      if (s1 == null)
          return s2;
      if (s2 == null)
          return s1;
      int len = Math.min(s1.length(), s2.length());
  
      // Find the index for the end of overlapping part
      int index = -1;
      for (int i = len; i &gt; 0; i--) {
          String substring = s2.substring(0, i);
          if (s1.endsWith(substring)) {
              index = i;
              break;
          }
      }
      StringBuilder sb = new StringBuilder(s1);
      if (index &lt; 0) 
          sb.append(s2);
      else if (index &lt;= s2.length())
          sb.append(s2.substring(index));
      return sb.toString();
  }
  </code></pre>