在Knuth-Morris-Pratt算法中，当“substring”单词是同一个字母的序列时，例如“AAAAAAAA…”，故障表的内容如下：“-1，0，1，2，3，4，5，…”。
这意味着如果测试类似于“aaaaaaaa B”，当我们到达“B”时，我们将返回X个字符并开始尝试再次匹配，尽管我们知道应该从B之后开始。
我遗漏了什么吗？
编辑（使示例具体化）：
假设测试是：aaaaaaaa b aaaaaaaaa，即（8as，b，9as），查找的单词是aaaaaaaa，即（9as）。
失败表将是：-1、0、1、2、3、4、5、6、7。
在某个点上，它将是m=0，i=8这将失败，所以m将变成m=m+i-t[8]=0+8-7=>m=1，而i将变成t[8]=7。
这将再次失败，所以现在我们有m=2，i=6，然后m=3，i=7，等等。
最佳答案
您将返回length(needle)个字符，但只在故障表给定的偏移量开始匹配在这种情况下，如果有7个A，而您在B上失败，T[7]将显示“跳过7个字符”，因此您将选中needle[7]与haystack[failed-length(needle)+7]（其中failed是草堆的索引，其中指针中的B与A相比）。因此它将在线性时间内运行，总是跳过已经匹配的7a中的6个的比较。一个更聪明的算法可能会向前跳一点，但只值更多的常数，因为它不能比线性更好。
关于algorithm - Knuth-Morris-Pratt算法的极端情况，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/20460601/