algorithm - Knuth-Morris-Pratt 算法极端情况

Question

在 Knuth-Morris-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 - T[8] = 0 + 8 - 7 => m = 1 并且 i 会是T[8] = 7.

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

Answer 1

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