KMP失效函数
我有一个关于 KMP 失效函数 f 的问题。假设图案的大小为 2^q，其中 q 大于或等于 8。
如果我知道 f(m/4) = 0，如何找到 f(m/2) 和 f(3m/4) 的值f(m) = 3m/4 提前？
我应该遵循什么样的策略？我想我或多或少了解了 KMP 算法，但我在这里找不到思考的方法。任何提示表示赞赏。
I have a question about KMP's failure function f. Assume that the size of the pattern is 2^q where q is bigger or equal to 8.
How can I find values of f(m/2) and f(3m/4) if I know f(m/4) = 0 and f(m) = 3m/4 in advance?
What kind of strategy I should follow? I think I get the KMP algorithm more or less but I can not find out a way to think here. Any hints are appreciated.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
我们知道f(m)=3m/4。因此，f(i)（其中 i 属于 {m/4;m}）必须等于 im/4（0 到 3m/4 之间的所有自然数）。
所以在这种情况下，f(m/2)=m/4（因为m/4=m/2-m/4）和f(3m/4)=m/2（因为m/2=3m/4-米/4)
We know that f(m)=3m/4. So, it is necessary that f(i), with i belonging to {m/4;m}, must be equal to i-m/4 (all natural numbers between 0 and 3m/4).
So in this case, f(m/2)=m/4 (because m/4=m/2-m/4) and f(3m/4)=m/2 (because m/2=3m/4-m/4)