Concatenate two strings without intersection

Question

I need to concatenate two string in another one without their intersection (in terms of last/first words).

In example:

"Some little d" + "little dogs are so pretty" = "Some little dogs are so pretty"

"I love you" + "love" = "I love youlove"

What is the most efficient way to do this in Java?

Answer 1

Here we go - if the first doesn't even contain the first letter of the second string, just return the concatenation. Otherwise, go from longest to shortest on the second string, seeing if the first ends with it. If so, return the non-overlapping parts, otherwise try one letter shorter.

 public static String docat(String f, String s) {
   if (!f.contains(s.substring(0,1)))
     return f + s;
   int idx = s.length();
   try {
     while (!f.endsWith(s.substring(0, idx--))) ;
   } catch (Exception e) { }
   return f + s.substring(idx + 1);
 }

 docat("Some little d", "little dogs are so pretty");
 -> "Some little dogs are so pretty"
 docat("Hello World", "World")
 -> "Hello World"
 docat("Hello", "World")
 -> "HelloWorld"

EDIT: In response to the comment, here is a method using arrays. I don't know how to stress test these properly, but none of them took over 1ms in my testing.

public static String docat2(String first, String second) {
  char[] f = first.toCharArray();
  char[] s = second.toCharArray();
  if (!first.contains("" + s[0]))
    return first + second;
  int idx = 0;
  try {
    while (!matches(f, s, idx)) idx++;
  } catch (Exception e) { }
  return first.substring(0, idx) + second;
}

private static boolean matches(char[] f, char[] s, int idx) {
  for (int i = idx; i <= f.length; i++) {
    if (f[i] != s[i - idx])
      return false;
  }
  return true;
}

Answer 2

Easiest: iterate over the first string taking suffixes ("Some little d", "ome little d", "me little d"...) and test the second string with .startsWith. When you find a match, concatenate the prefix of the first string with the second string.

Here's the code:

String overlappingConcat(String a, String b) {                              
  int i;
  int l = a.length();
  for (i = 0; i < l; i++) {
    if (b.startsWith(a.substring(i))) {
      return a.substring(0, i) + b;
    }
  }
  return a + b;
}

The biggest efficiency problem here is the creation of new strings at substring. Implementing a custom stringMatchFrom(a, b, aOffset) should improve it, and is trivial.