KMP算法的时间复杂度为什么是O(n)
哪位大牛能给个详细的解释吗？
展开
收起
版权声明：本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
2
条回答
写回答
-
主串T，比较串P，
由于KMP算法的思想是主串不回溯的简化算法，执行的时候呢在串比较的扫描里面要么执行POST和POSP，要么执行NEXT[]数组的右移，然后比较，所以字符比较最多就是为O（LenthT）,即不会超过O（n）
其实KMP看起来很吓人，但是你抓住它的思想“主串不回溯”就很简单了.
给你网上的详细解释:http://sundful.javaeye.com/blog/2638472019-07-17 22:55:52赞同 展开评论 -
Nothing for nothing.主串T，比较串P，
由于KMP算法的思想是主串不回溯的简化算法，执行的时候呢在串比较的扫描里面要么执行POST和POSP，要么执行NEXT[]数组的右移，然后比较，所以字符比较最多就是为O（LenthT）,即不会超过O（n）
其实KMP看起来很吓人，但是你抓住它的思想“主串不回溯”就很简单了.
KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt同时发现，因此人们称它为克努特——莫里斯——普拉特操作（简称KMP算法）。KMP算法的关键是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是实现一个next()函数，函数本身包含了模式串的局部匹配信息。2019-07-17 22:55:52赞同 展开评论
相关问答