多次出现的 KMP 算法
是否仍然可以执行 O(n) 时间复杂度来搜索多次出现的 Knuth-Morris-Pratt 算法？
Is it possible to still perform a O(n) time complexity to search multiple occurrences of Knuth–Morris–Pratt algorithm?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
假设我们有一个字符串 S[0,...,N]。回想一下，前缀数组中的第 i 个条目存储与后缀匹配的 S[0,...,i] 的最大前缀的长度。
我们可以计算模式$subject的前缀数组P（假设$在subject中不出现）。仍然需要找到 P[i]==length(pattern) 的索引，这可以在线性时间内完成。
Suppose we have a string S[0,...,N]. Recall that the ith entry in the prefix array stores the length of the maximal prefix of S[0,...,i] that matches the suffix.
We can calculate the prefix array P for pattern$subject (assuming that $ doesn't occur in subject). It remains to find indices such that P[i]==length(pattern), which can be done in linear time.