string - 了解 Knuth Morris Pratt (KMP) 失效函数

Question

我一直在阅读 Wikipedia article about the Knuth-Morris-Pratt algorithm我对如何在跳转/部分匹配表中找到这些值感到困惑。

  i  |  0  1  2  3  4  5  6
W[i] |  A  B  C  D  A  B  D
T[i] | -1  0  0  0  0  1  2

如果有人能更清楚地解释shortcut rule 因为这句话

"let us say that we discovered a proper suffix which is a proper prefix and ending at W[2] with length 2 (the maximum possible)"

令人困惑。如果正确的后缀以 W[2] 结尾，它的大小不是 3 吗？

另外我想知道为什么当存在大小为 1 的前缀和后缀时 T[4] 不是 1:A。

感谢您提供的任何帮助。

Answer 1

请注意，故障函数 T[i] 不使用 i 作为索引，而是作为长度。因此，T[2]表示W的前两个字符组成的字符串的最长固有边界(既是前缀又是后缀的字符串)的长度，而不是以字符结尾的字符串形成的最长固有边界2. 这就是为什么 T[2] 的最大可能值是 2 而不是 3 - 由 W 的前两个字符组成的子串的长度不能大于 2。

使用这种解释，也更容易理解为什么 T[4] 是 0 而不是 1。由 W 的前四个字符组成的 W 的子串是 ABCD，它没有适当的前缀也是适当的后缀。

希望这对您有所帮助!