Knuth-Morris-Pratt算法

是Knuth-Morris-Pratt算法的解决方案：Haystack：AAAAAAAAAA，针：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; } 

Answer 1

KMP专注于在完全匹配搜索失败时优化搜索，但可以重复使用部分匹配来重新开始搜索，而不是使用简单的方法。 但是，您提供的案例没有部分匹配，它始终在每次搜索迭代时找到完整的单词。 所以我确实希望KMP为你提议的案例返回3场比赛。 请注意，这是一个边缘情况，可能会想要修改算法以利用干草堆或单词或两者的上下文信息，但您现在超越了KMP。 希望这可以帮助。