KMP算法理解与实现

KMP算法——字符串匹配算法

Ep：如果给定两个字符串，规定（搜索的文章）是搜索串，（关键字）是模板串，例子如下：

在c中寻找是否寻在a，如果存在，返回开始的位置

一般来说，我们会想到的方法就是，c中一个字符串一个字符串比较，如果一样就比较下一个，这样的方法称为暴力破解，假设搜索串长度为M,模板串长度为N,则复杂度为O（M*N）。

KMP算法的核心同类文章

https://kb.cnblogs.com/page/176818/

https://blog.csdn.net/starstar1992/article/details/54913261

定义一个Next【】数组，长度为模板串长度，分别表示当前字符串引入前N个元素。

数组内存放当字符串引入前N个元素的时候，前缀串和后缀串的相同个数。

next【】数组内存储最长前后缀长度，假定初始值next【0】= -1 模板串a的next【7】分别为【-1，-1,0,1,2，-1，-1】

举个例子，当next为4的时候next【4】=2，此时的字符串是ababa，前缀后缀相同的部分为aba，三个元素，由于初始为-1，所以最终结果为2【使用-1是因为这样定义比如当匹配k的时候不满足可以直接令k=next【k】，刚好是相同前缀结束的地方。

kmp算法和next原理大致相同。核心是用模板串去匹配字符串，外部循环是每次搜索字符串指针q向后移动1，循环内部如果模板串的第一个字符k和搜索串的某一个时刻所指字符串相同，模板串k+1，搜索串q+1；如果不同，模板串回退到相同前缀结束的地方，代码表现为k=next【k】，如果已经回退到最开始的地方即k=-1，相当于一切重头开始。如果某个时刻k的值等于模板串长度-1（因为k初值为-1，每次匹配成功一个字符就+1，最多可以变成len-1），则证明完全匹配成功，返回当前所指向的值。

求next代码如下