解决方案是Knuth-Morris-Pratt 算法 https://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm:干草堆:AAAAAAAAA,针:AAA,即:3,对吗?
因为,大海捞针中有 8 个 AAA 实例,但据我了解,knuth-morris-pratt 算法只能找到 3 个。我的想法错了吗?
这个问题可以通过找出字符串中每个后缀的边界来解决吗?
以下是我对KMP算法的实现:
public static int occurrenceOfSubstring(char[] target, char[] pattern) {
int[] overlay = new int[pattern.length];
overlay[0] = -1;
overlay[1] = 0;
int i = 0, j = 1;
while (j + 1 < pattern.length) {
if (pattern[i] == pattern[j]) {
if (i == 0) {
overlay[j + 1] = 1;
} else {
overlay[j + 1] = overlay[j] + 1;
}
i++;
j++;
} else if (pattern[j] == pattern[0]) {
i = 0;
} else {
j++;
}
}
int l = 0,count=0;
for (int k = 0; k < target.length; k++) {
if (target[k] == pattern[l]) {
if (l == pattern.length - 1) {
l = 0;
count++;
} else {
l++;
}
} else {
l = overlay[l] == -1 ? 0 : overlay[l];
}
}
return count;
}
KMP 专注于在完全匹配搜索失败时优化搜索,但与简单的方法相比,可以重用部分匹配来重新启动搜索。然而,您提供的情况没有部分匹配,它总是在每次搜索迭代时找到完整的单词。因此,我确实希望 KMP 针对您提出的案例返回 3 个匹配项。请注意,这是一种边缘情况,人们可能会想修改算法以利用大海捞针或单词或两者的上下文信息,但您现在超出了 KMP 的范围。希望这可以帮助。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)