4

我一直在阅读有关 Knuth-Morris-Pratt 算法的 Wikipedia 文章，我对如何在跳转/部分匹配表中找到这些值感到困惑。

  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.

感谢您提供的任何帮助。

4

2 回答 2

7

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

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

希望这可以帮助！

于 2013-02-06T20:40:47.530 回答
0

“假设我们发现了一个适当的后缀，它是一个适当的前缀，以 W[2] 结尾，长度为 2（可能的最大值）”

好的，长度可以最大为 2，这是正确的，这就是为什么......一个事实：“正确”前缀不能是整个字符串，“正确”后缀也是如此（如正确子集）

让， W[0]=AW[1]=AW[2]=A ，即模式是“AAA”，因此，（最大长度）正确的前缀可以是“AA”（从左到右），并且（最大长度）正确的后缀可以是“AA”（从右到左）//是的，前缀和后缀有重叠（中间的“A”）

因此，该值将是 2 而不是 3，仅当前缀不正确时才会为 3。

于 2014-07-02T20:09:48.870 回答