kmp算法难吗是什么级别

Question

如题所述

Answer 1

KMP算法是我们数据结构串中最难也是最重要的算法。难是因为KMP算法的代码很优美简洁干练，但里面包含着非常深的思维。真正理解代码的人可以说对KMP算法的了解已经相当深入了。而且这个算法的不少东西的确不容易讲懂，很多正规的书本把概念一摆出直接劝退无数人。这篇文章将尽量以最详细的方式配图介绍KMP算法及其改进。文章的开始我先对KMP算法的三位创始人Knuth,Morris,Pratt致敬，懂得这个算法的流程后你真的不得不佩服他们的聪明才智。

Answer 2

KMP算法真的有这么难吗？（清晰详细版） 原创
2022-09-08 17:14:43
1点赞

三金C_C

码龄2年

关注
KMP算法我一年之前就接触了，但由于实在难以理解next[]求法故放弃，每次做一次字符串匹配的时候，很多情况下都是暴力解决，除了极个别情况把next[]求法背成模板求解AC。
注意：KMP算法已经成为了数据结构考研大纲中了。

最近由于是刷题，再一次碰到了KMP算法，同时学院课程《算法设计与分析》也探讨了KMP算法，这让我不得不进行重新思考。翻遍大量的资料，其中就有CSDN传播最广的文章，有兴趣的可以查看从头到尾彻底理解KMP（2014年8月22日版）但是上面博客实在是太长了，虽然很好，但是看起来真的很吃力。特别是一开始就给你KMP定义让人很难读下去。同时也很有很多博客，一开始就给你next[]的定义，非常突兀。

本篇博客立足于算法初学者，从预备知识到next数组的引出，再到推导公式，最后给出代码**。这是一篇快速掌握并且十分简洁的KMP算法博客。**

我了解到next[]代码部分和手写next[]根本就不是一个思路。很多教辅也只会教手写部分，但手写next[]主要是进行比较前后缀最大相等长度，但是代码部分就根本没有这一思想，主要是数学归纳与推导证明，个人感觉，十分具有挑战性，毕竟我本人光next[]也看了很久。所以，一开始接触kmp，特别是企图求next数组的不要担心与焦虑，这将是一篇让你彻底明白为什么有next[]以及kmp原理等的博客。

希望本篇博客对你有所帮助！

Answer 3

kmp算法特点主要是减少字符串查找过程中的回退，尽可能减少不用的操作，算法复杂度是O(n+m)。思想可以使用与ac自动机