KMP算法解说的很多，清晰的很少，在此写一个汪汪都能看懂的通俗易懂直观的精讲。文末会给出学习倡议。

KMP算法的由来和本文术语解释

KMP算法的中文名称为疾速模式匹配算法，是为了疾速解决在一个字符串中查找另一个字符串的问题。（为了不便形容，要找到的那个字符串叫模式串，要搜寻的那个范畴叫文本串。比方要求在字符串abbaf中找到字符串baf，baf就是模式串，abbaf就是文本串）。

针对这种问题，咱们其实很容易想到一种暴力的算法，那就是一个一个比。

不难发现，遇到不匹配的状况时，模式串每次都是傻傻的挪一下，而后再一位一位地去比拟。

暴力太傻了吧，所以就有了KMP算法，让模式串迈开腿，可能大步往前走。但大步走也不是瞎走，不然走过了相等的村就没有相等的店了，得有点策略地走，于是有了next数组。这个数组的名字起的其实还是有点形象的，代表比到某一位不匹配了下一个比哪一位，像一个领导手册似的。

为什么要有next数组以及对他的直观了解

next数组就是一个模式串的行为领导手册。

当红色的C和A不匹配时，黄色的AB和AB曾经比拟过了，而模式串p中橙色和黄色局部是相等的，那挺好，黄色AB都跟文本串比过了，橙色的AB就能够省点事，这样间接比拟绿色箭头处就能够了。

那咱们怎么决定从哪一位开始比拟呢。这里就引入了前后缀的问题。要找到模式串p中不匹配地位A后面的子串"ABCAB"中雷同的前缀和后缀，这个雷同的局部就是能够偷懒不必比的局部了。那如果雷同的前缀和后缀有很多取哪个呢？那必定取最长的呀，这样就能偷更多懒，下一轮不必比的就更多了。

所以，为了晓得如何偷懒，咱们定义了一个没有名字的表，这个表通知咱们以某个地位的字符结尾的字符串，最长的雷同前后缀的长度是多少。

看下图了解最长雷同前后缀。

那为啥要晓得长度呢？长度其实就是下一次的下标。以下图为例，A后面以B为结尾的字符串ABCAB的最长雷同前后缀的长度为2，那下一轮比拟的就是2地位的C，后面的不必比了。

那么这个时候next数组就出场了，他就和这个不出名的表有关系，但又不齐全一样，但实质上next都是由这张表变来的。

理论实现时依据须要可能把这个表的所有元素-1，也可能所有元素右移之类的(右移的话AC不匹配时就不必看前一位的next了，间接看本人地位的就行，因为他人的右移到本人的地盘了)。我也不晓得为啥就要-1之类的，除了让KMP更难了解以外，如同啥用没有。

本文就不进行这些花里胡哨的操作了。

精髓！next数组的代码实现图预警

到当初大部分人预计都能手写一个模式串的next的数组了，毕竟肉眼看最长的雷同前后缀也还行。然而看到代码实现的时候还是会懵的不行，这是因为真的太奇妙了，其中甚至用到了递归的思路。为了好了解，我就间接将前文图中推导的表作为next数组。

递归思路如何画图了解

1.定义两个指针，cur是指向以后地位的，代表要求以cur地位字符结尾的最长雷同前后缀，recur有两个含意，可能是上一轮循环之后传过来的（代表以前一个字符结尾的最长雷同前后缀），也可能是递归的时候递归到的，反正也不必管这么多，反正recur在赋值给next时候就会指向最长雷同前缀的下一位。

2.画图了解递归的思路

如图显示的是进入某一轮循环，cur=17,recur=8时递归代码的执行过程。

next[cur-1]= next[16] = 8代表红色的两个框雷同（时刻牢记next的含意）

如果这个时候s[cur] == s[recur]阐明next[cur] = recur+1=9,示意最长雷同前后缀长度为9。
如果这个时候s[cur] != s[recur]阐明next[cur] <= recur,这里就要用到递归了。红色框中字符相等，咱们求的最长雷同后缀是以cur结尾的那一撮，那就能够转化为求recur-1结尾的最长雷同前后缀,即next[recur-1]。依据next[recur-1]=next[7]的值3能够晓得右边两个绿框雷同，所以图中四个绿框就都雷同了。然而咱要的其实还是左右边上的两个绿框相等。
接下来就还是循环第一步，recur指针移到新的红色地位。如果这时next[cur] == next[recur]的话，next[cur] = recur+1=4。如果不相等，那recur还要递归挪动，直到recur = 0时不能再挪动或者遇到相等的状况。

void getNext(int* next,string& s){        int recur = 0;        next[0] = recur;        for(int cur = 1;cur < s.size();cur++){            while(recur > 0 && s[cur] != s[recur]){                recur = next[recur-1];//递归局部            }            if(s[cur] == s[recur]){//recur=0或者相等的时候                recur++;            }            next[cur] = recur;        }    }

计算next时初始化值如何确定

另外，代码的初始条件也不能看着答案想当然。next[0]=0是因为只有s[0]一个元素时，不存在最长雷同前后缀。j的初始化有两种方法能够思考，一种是察看for循环中的next[i]=j，所以next[0]=0时j就是0。也能够在计算next[1]的时候看看，须要j是几能力失去正确答案。

计算结果的图形化解释

以字符串"ABCABA"为例运行代码，两头过程如下图。

KMP算法的代码实现

利用next实现KMP的要害要点

有了next数组之后，如何利用他呢？大体来说是管制模式串指针和文本串指针的挪动，直到达到文本串开端或者模式串开端。其中有以下几个要点：

遇到某一位不匹配时，要依据这一位前一位的next值确认接下来要比拟的是模式串中的哪一位(也就是模式串指针指向哪里)。
1中扭转了模式串指针之后，文本串指针不能挪动到下一位，而是要放弃不变，持续比拟，否则就会越过一些值。所以for外部须要有while循环，而不能写if让其进入下一轮for循环。

    int j = 0;        for(int i = 0;i < haystack.size();i++){            while(j > 0 && needle[j] != haystack[i]){//对应要点2的while循环                cout << "pattern[" << j << "]" << "!=" << "s[" << i << "]" << endl;                cout << "j从" << j << "变为" << next[j-1] << endl;                j = next[j-1];//对应要点1的找前一位            }            if(needle[j] == haystack[i]){                cout << "pattern[" << j << "]" << "==" << "s[" << i << "]" << endl;                j++;            }            if(j == needle.size()) return i - needle.size()+1;//完结坐标-长度+1=起始坐标        }

运行后果的图形化解释

退出必要的正文运行，后果如下，与图片齐全对应。

pattern[0]==s[0]pattern[1]==s[1]pattern[2]==s[2]pattern[3]==s[3]pattern[4]==s[4]pattern[5]!=s[5]j从5变为2pattern[2]==s[5]pattern[3]==s[6]pattern[4]==s[7]pattern[5]==s[8]

最初的学习倡议

找个很长的字符串，按我的推导把getNext函数人工推导一次，这样就拿了解recur变动的奇妙之处了。当递归不好了解时，肯定要联合解释递归的那两个红框和绿框去思考。