问KMP的失效函数
EN

Stack Overflow用户

提问于 2011-10-25 06:31:07

回答 1查看 356关注 0票数 0

我有一个关于KMP的失效函数f的问题。假设模式的大小是2^q，其中q大于或等于8。

如果我事先知道f(m/4) =0和f(m) = 3m/4，如何找到f(m/2)和f(3m/4)的值？

我应该遵循什么样的策略？我想我或多或少得到了KMP算法，但我找不到一种在这里思考的方法。任何提示都是值得感谢的。

回答已采纳

发布于 2011-10-25 15:24:36

我们知道f(m)=3m/4。因此，f(i)，其中i属于{m/4;m}，必须等于i-m/4 (0到3m/4之间的所有自然数)。所以在这种情况下，f(m/2)=m/4 (因为m/4=m/2-m/4)和f(3m/4)=m/2 (因为m/2=3m/4-m/4)

票数 0

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/7882725

复制

相似问题

问KMP的失效函数EN