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

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

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

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

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

字串定位为串的模式匹配，求的是子串（常称为模式串）在主串的位置。以下是暴力求法，这是数据结构中关于string的定义：