java - 从两个字符串中查找相似子字符串的方法

Question

我正在使用这段 Java 代码来查找类似的字符串：

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

但是有了它str1 = "pizzabase"并str2 = "namedpizzaowl"不起作用。

我如何找到常见的子字符串，即“pizza”？

Answer 1

遍历每个字母 in str1，检查它是否存在于str2. 如果它不存在，则转到下一个字母，如果存在，则将str1您检查的子字符串的长度str2增加到两个字符，然后重复直到找不到更多匹配项或您已经遍历str1.

这将找到共享的所有子字符串，但是 - 就像冒泡排序一样 - 几乎不是最优的，而是如何解决问题的非常基本的示例。

像这个伪ish示例：

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 。