我一直在读的对维基百科的文章克努特 - 莫里斯 - 普拉特算法我感到困惑值如何被发现的跳/部分匹配表。

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

如果有人能更清楚地解释快捷规则，因为这句话

让我们说，我们发现了一种适当的后缀是一个适当的preFIX和结束为W [2]，长度2（最大可能的）

是混乱的。如果适当的后缀为W结束[2]，那岂不是的大小？

此外，我不知道为什么T [4]不为1时，有一个preFIX大小为1和后缀：该A.

感谢您可以提供任何帮助。

注意，失败函数T [我]不使用我作为一个指标，而是作为一个长度。因此，T [2]重presents最长的适当边界的长度（一个字符串，既是preFIX和后缀）从W的前两个字符组成的字符串，而不是最长的适当边界通过在字符2.这是为什么T的最大可能值[2]是2-而非3结束字符串形成。 - 从W的前两个字符形成不能有长度大于2的任何更大的子

使用这个跨pretation，它也更容易看到为什么T [4]为0而不是1 W的子串，从W的前四个字符组成是ABCD，其中有没有适当的preFIX这也是一个正确的后缀。

希望这有助于！

I've been reading the Wikipedia article about the Knuth-Morris-Pratt algorithm and I'm confused about how the values are found in the jump/partial match table.

  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

If someone can more clearly explain the shortcut rule because the sentence

"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)"

is confusing. If the proper suffix ends at W[2] wouldn't it be size of 3?

Also I'm wondering why T[4] isn't 1 when there is a prefix and suffix of size 1: The A.

Thanks for any help that can be offered.

Notice that the failure function T[i] does not use i as an index, but rather as a length. Therefore, T[2] represents the length of the longest proper border (a string that is both a prefix and suffix) of the string formed from the first two characters of W, rather than the longest proper border formed by the string ending at character 2. This is why the maximum possible value of T[2] is 2 rather than 3 - the substring formed from the first two characters of W can't have length any greater than 2.

Using this interpretation, it's also easier to see why T[4] is 0 rather than 1. The substring of W formed from the first four characters of W is ABCD, which has no proper prefix that is also a proper suffix.

Hope this helps!