我一直在读关于 Knuth-Morris-Pratt 算法的维基百科文章 http://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_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 作为索引,而是作为长度。因此,T[2]表示W的前两个字符组成的字符串的最长固有边界(既是前缀又是后缀的字符串)的长度,而不是以字符结尾的字符串形成的最长固有边界的长度2. 这就是为什么 T[2] 的最大可能值为 2 而不是 3 - 由 W 的前两个字符形成的子字符串的长度不能大于 2。
使用这种解释,也更容易理解为什么 T[4] 是 0 而不是 1。由 W 的前四个字符组成的 W 的子串是 ABCD,它没有正确的前缀,但也是正确的后缀。
希望这可以帮助!
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)