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

Question

我一直在阅读关于Knuth-Morris-Pratt算法的维基百科文章,我对如何在跳转/部分匹配表中找到值感到困惑.

  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

如果有人可以更清楚地解释因为句子的快捷方式规则

"让我们说我们发现了一个正确的后缀,它是一个正确的前缀,结束于W [2],长度为2(最大可能)

令人困惑.如果正确的后缀在W [2]结束,它的大小不是3吗？

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

感谢您提供的任何帮助.

Answer 1

请注意,失败函数T [i]不使用i作为索引,而是使用长度.因此,T [2]表示由W的前两个字符形成的字符串的最长的适当边界(既是前缀和后缀的字符串)的长度,而不是由字符串结尾的字符串形成的最长的正确边界. 2.这就是为什么T [2]的最大可能值是2而不是3 - 由W的前两个字符形成的子串不能具有大于2的长度.

使用这种解释,也更容易理解为什么T [4]为0而不是1.从W的前四个字符形成的W的子串是ABCD,它没有正确的前缀也是正确的后缀.

希望这可以帮助!