Knuth-Morris-Pratt算法角例

Question

在Knuth Pratt算法中，当“子串”字是一个序列的字母时，例如。“AAAAAAAA.”，故障表如下："-1，0，1，2，3，4，5，.“。

这意味着，如果测试类似于"AAAAAAAB“，当我们到达" B”时，我们将返回X字符并开始重新匹配，尽管我们知道我们应该在B之后开始。

我是不是遗漏了什么？

编辑(使示例具体化)：

假设测试是: AAAAAAAABAAAAAAAAA，即(8 As，B，9 As)，查找的单词是AAAAAAAAA，也就是(9 As)。

失败表将是：-1，0，1，2，3，4，5，6，7。

在某个时刻，它将是m= 0，i= 8，这将失败，因此m将变成m=m+i- T8 =0+8-7 => m=1，而i将是T8 = 7。

这将再次失败，所以现在我们有m= 2，i= 6，然后m= 3，i= 7，等等。

Answer 1

您将返回length(needle)字符，但只会在failure表给出的偏移量处开始匹配。在这种情况下，如果B上有7A而您失败了，T[7]会说“跳过7个字符”，所以您可以检查needle[7]和haystack[failed-length(needle)+7] (其中失败是大海捞针中B与A比较的索引)。因此，它将以线性时间运行，总是跳过你已经匹配的7A中的6个比较。一个更聪明的算法可能会跳过更多，但只有更多的常量，因为它不能比线性更好。