Объединить две строки без пересечения

Question

Мне нужно объединить две строки в другую без их пересечения (в терминах последних / первых слов).

Например:

"Некоторые маленькие д" + "маленькие собачки такие красивые" = "Некоторые маленькие собачки такие красивые"

"Я люблю тебя" + "люблю" = "Я люблю тебя, любовь"

Какой самый эффективный способ сделать это на Java?

Answer 1

Здесь мы идем - если первая даже не содержит первую букву второй строки, просто верните конкатенацию.В противном случае переходите от самой длинной к самой короткой второй строке, чтобы увидеть, заканчивается ли первая из них.Если это так, верните непересекающиеся части, в противном случае попробуйте на одну букву короче.

 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"

РЕДАКТИРОВАТЬ: В ответ на комментарий, здесь метод с использованием массивов.Я не знаю, как правильно провести стресс-тестирование, но ни один из них не занял более 1 мс в моем тестировании.

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

Вы можете избежать создания ненужных подстрок с помощью метода regionMatches ().

public static String intersecting_concatenate(String a, String b) {
    // Concatenate two strings, but if there is overlap at the intersection,
    // include the intersection/overlap only once.

    // find length of maximum possible match
    int len_a = a.length();
    int len_b = b.length();
    int max_match = (len_a > len_b) ? len_b : len_a;

    // search down from maximum match size, to get longest possible intersection
    for (int size=max_match; size>0; size--) {
        if (a.regionMatches(len_a - size, b, 0, size)) {
            return a + b.substring(size, len_b);
        }
    }

    // Didn't find any intersection. Fall back to straight concatenation.
    return a + b;
}

Answer 3

Самый простой: переберите первую строку с суффиксами ("Some little d", "ome little d", "me little d" ...) и протестируйте вторую строку с помощью .startsWith.Когда вы найдете совпадение, объедините префикс первой строки со второй строкой.

Вот код:

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;
}

Самой большой проблемой эффективности здесь является создание новых строк в substring.Реализация пользовательского stringMatchFrom(a, b, aOffset) должна улучшить его, и это тривиально.

Answer 4

Создайте дерево суффиксов первой строки, затем обойдите дерево от корня, взяв символы из начала второй строки и отслеживая самый длинный найденный суффикс.

Это должен быть самый длинный суффикс первой строки, который является префиксом второй строки. Удалите суффикс, затем добавьте вторую строку.

Все это должно быть возможно в линейном времени вместо квадратичного времени, необходимого для циклического прохождения и сравнения всех суффиксов.

Answer 5

isBlank(CharSequence), join(T...) и left(String, int) являются методами от Apache Commons.

public static String joinOverlap(String s1, String s2) {
    if(isBlank(s1) || isBlank(s2)) { //empty or null input -> normal join
        return join(s1, s2);
    }

    int start = Math.max(0, s1.length() - s2.length());

    for(int i = start; i < s1.length(); i++) { //this loop is for start point
        for(int j = i; s1.charAt(j) == s2.charAt(j-i); j++) { //iterate until mismatch
            if(j == s1.length() - 1) { //was it s1's last char?
                return join(left(s1, i), s2);
            }
        }
    }

    return join(s1, s2); //no overlapping; do normal join
}

Answer 6

Следующий код работает для первого примера. Я не проверял это подробно, но вы поняли. Он в основном ищет все вхождения первого символа secondString в firstString, так как это единственные возможные места, где может происходить перекрытие. Затем он проверяет, является ли остаток первой строки началом второй строки. Вероятно, код содержит некоторые ошибки, когда не обнаружено совпадений, но это была скорее иллюстрация моего ответа

String firstString = "Some little d";
String secondString = "little dogs are so pretty";
String startChar = secondString.substring( 0, 1 );
int index = Math.max( 0, firstString.length() - secondString.length() );
int length = firstString.length();
int searchedIndex = -1;
while ( searchedIndex == -1 && ( index = firstString.indexOf( startChar, index ) )!= -1 ){
  if ( secondString.startsWith( firstString.substring( index, length ) ) ){
    searchedIndex = index;
  }
}
String result = firstString.substring( 0, searchedIndex ) + secondString;