开发者社区

文档建议反馈控制台

文章/答案/技术大牛

发布

社区首页 >问答首页 >用于多次出现的KMP算法

问用于多次出现的KMP算法
EN

Stack Overflow用户

提问于 2011-10-19 18:41:24

回答 1查看 1.6K关注 0票数 3

是否仍然可以执行O(n)时间复杂度来搜索Knuth-Morris-Pratt算法的多次出现？

pattern-matching

EN

回答 1

Stack Overflow用户

回答已采纳

发布于 2011-10-19 21:17:52

假设我们有一个字符串S0，...，N。回想一下，前缀数组中的第i个条目存储了与后缀匹配的S0，...，i的最大前缀的长度。我们可以计算模式$subject的前缀数组P(假设$没有出现在subject中)。它仍然需要找到Pi==length(模式)这样的索引，这可以在线性时间内完成。

票数 2

EN

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

原文链接：

https://stackoverflow.com/questions/7820024

复制

相似问题