我一直在阅读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
如果有人能更清楚地解释捷径规则
“让我们说，我们发现了一个适当的后缀，它是一个适当的前缀，以W（2）结尾，长度为2（最大可能）”。
令人困惑。如果正确的后缀以w[2]结尾，它的大小不是3吗？
另外，我想知道为什么当有大小为1的前缀和后缀时T[4]不是1:a。
谢谢你的帮助。
最佳答案
请注意，故障函数T[i]没有使用i作为索引，而是使用i作为长度因此，T[2]表示由W的前两个字符组成的字符串的最长真边框（既为前缀又为后缀的字符串）的长度，而不是由以字符2结尾的字符串组成的最长真边框这就是为什么T（2）的最大可能值是2而不是3——由W的前两个字符所形成的子串不能具有大于2的长度。
使用这种解释，也更容易理解为什么T[4]是0而不是1由w的前四个字符构成的w的子串是abcd，它没有合适的前缀，也没有合适的后缀。
希望这有帮助！
关于string - 了解Knuth Morris Pratt(KMP)失效函数，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/14738130/