1

在 Knuth-Morris-Pratt 算法中，当“子串”词是相同字母的序列时，例如。“AAAAAAA...”，故障表是这样的：“-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，等等。

4

1 回答 1

2

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

于 2013-12-08T23:49:53.653 回答