Способ поиска похожих подстрок из двух строк

Question

Я использую этот фрагмент кода Java для поиска похожих строк:

if( str1.indexof(str2) >= 0 || str2.indexof(str1) >= 0 ) .......

, но с str1 = "pizzabase" и str2 = "namedpizzaowl" он не работает.

как мне найти общие подстроки, т.е. "пицца"?

Answer 1

Перебирать каждую букву в str1, проверяя ее существование в str2.Если он не существует, перейдите к следующей букве, если это так, увеличьте длину подстроки в str1, которую вы проверяете в str2, до двух символов и повторяйте, пока не будут найдены другие совпадения, или выперебрал str1.

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

Примерно такПример псевдо-выхода:

pos = 0
len = 1
matches = [];

while (pos < str1.length()) {

    while (str2.indexOf(str1.substring(pos, len))) {
       len++;
    }

    matches.push(str1.substring(pos, len - 1));
    pos++;
    len = 1;
}

Answer 2

Если ваш алгоритм говорит, что две строки похожи, когда они содержат общую подстроку, то этот алгоритм всегда будет возвращать true;пустая строка "" является тривиальной подстрокой каждой строки.Также имеет смысл определить степень сходства между строками и вернуть число, а не логическое значение.

Это хороший алгоритм для определения строки (или, в более общем случае, последовательности)сходство: http://en.wikipedia.org/wiki/Levenshtein_distance.