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

Question

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

В примере:

«Некоторые маленькие г» + «маленькие собаки так красиво» = «Некоторые маленькие собаки настолько симпатичны»

«Я люблю тебя» + «любовь» = «Я люблю youlove "

Что представляет собой самый эффективный способ сделать это в 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" 

EDIT: В ответ на комментарий здесь приведен метод использования массивов. Я не знаю, как правильно проверить тест, но ни один из них не взял на себя 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

Простейший: проведите по первой строке с суффиксами («Немного 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 3

Следующий код, похоже, подходит для первого примера. Я не тестировал его широко, но вы понимаете. Он в основном ищет все вхождения первого символа 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; 

Answer 4

Вы можете избежать создания ненужных подстроки с 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 5

isBlank(CharSequence), join(T...) и left(String, int) методы из Apache общин.

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

suffix tree Создания первой строки, а затем перемещаться по дереву от корня принимают символы с начала второй строки и отслеживанием самого длинного суффикса найденным.

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

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