KMP算法
关键字： 模式匹配 前缀 后缀 next数组
应用：查找串T是否为串S的子串
时间复杂度：O(n+m)
主要内容：
1、前缀和后缀；
2、KMP模式匹配简单描述；
3、递推求next数组；
4、结合代码实现；
1、前缀和后缀
前缀：除了最后一个字符外，一个字符串的全部头部组合；
后缀：除了第一个字符以外，一个字符串的全部尾部组合；
例如S串：ACADBDACA
所有前缀：{“A”、”AC”、”ACA”、”ACAD”、”ACADB”、”ACADBD”、”ACADBDA”、”ACADBDAC”}；
所有后缀：{“A”、”CA”、”ACA”、”DACA”、”BDACA”、”DBDACA”、”ADBDACA”、”CADBDACA”}；
前后缀相同的有：{“A”、”ACA”}；
有什么用？
我们知道，普通的字符串匹配如果遇到失配的情况，那么只能放弃前面所有已经匹配过的字母，重新将匹配串的第一个字母放到模式串中当前匹配串第一个字母所对应模式串位置的下一个位置。
但是这样的算法复杂度最坏情况下达到了O(n*m)
因此，可以得出暴力匹配最大的缺点是在比较的时候产生了很多不必要的比较冗余。如果我们每次如果能根据匹配串自身的一些特性，把失配情况下重新滑到第一个位置变成慢慢回溯。。。这会变成怎么样呢？
2、KMP模式匹配简单描述
举个例子来说，假如：
S串：BBC ABCDAB ABCDABCDABDE
T串：ABCDABD
在S串与T串的匹配过程中，如果遇到了如下的情况
即T[0]T[1]…T[5] == S[3]S[4]…S[8] 但是T[6] ≠S[9]
我们可以发现，如果在T串中，满足如下条件：
T[0]T[1]…T[p-1]== T[k-p+1]T[k-p+2]…T[k]
即在串T中，长度为p的前缀与后缀是相等的（注意这里我们再一次提到了前缀和后缀）
在这个例子中刚好存在当p=2,k=5的时候有
T[0]T[1] ==T[4]T[5]
那么当T串遇到第k+1个位置与S串失配的话，T串的指针j此时可以进行回溯
先来比较一下：
在普通算法中S串的指针i需要退回到S[4]，而T串的指针j则直接退回到T[0]；
在KMP算法中i不需要进行任何改变，只需要j回溯到next[j]的位置（即退回到T[2]）；
也就是说此时next[6] = 2 （注意此时j=6）
即我们可以得到这样一个公式：
移动位数 = 已匹配的字符数 - 对应的部分匹配值
详细匹配过程见链接：https://kb.cnblogs.com/page/176818/
那么其实我们只要在S串与T串匹配之前，对T串进行预处理一遍，求出next数组，对于每次失配的情况，正确地利用T串自身性质慢慢进行回溯，就可以达到O(n+m)的时间复杂度，大大提高字符串匹配的效率。
3、递推求next数组
那么如何求出这个next数组？
递推求解：假设T串的子串为T’，长度为k
当k=1时
很明显next[0]=0
当k=2时
如果满足T[0] == T[1] 那么
next[1] = next[0] + 1
否则
next[1] = 0
….
当k=q+1时，如果存在一个数p使得next[q]== p 即等同于满足
T[0]T[1]…T[p-1]== T[q-p+1]T[q-p+1]…T[q]
那么 next[k] = p + 1
也就是说 next[q+1] = next[q] + 1
否则的话让next[p] 与T’串的后缀再一次进行比较
也就是说如果存在一个数f使得next[p] == f 即等同于满足
T[0]T[1]…T[f-1] == T[q-f+1]T[q-f+2]…T[q]
那么 next[q+1] = f + 1;
也就是说 next[q+1] = next[p] + 1;
也等同于 next[q+1] = next[next[q]] + 1;
…
否则
next[q+1] = 0
下面是递推的匹配示意图和过程
其中注意下面所述的S串实质上是上面提到的T串，即模式串
结合到一个循环中去得到伪代码
while j >=0 if S[j] == S[p] Then next[p+1] = next[j]+1; break; j = next[j];这也就是KMP算法的核心！！！
4、结合代码实现
第一种风格：
void getNext(){ memset(next,0,sizeof(next)); //初始化所有数据为0 for(int i=1;i<m;i++) //串长为m（0~m-1) { int j=next[i]; //从第二个位置开始 while(j&&T[i]!=T[j]) //如果j的值不为0并且当前是失配状态 j=next[j]; //指针跳跃,直到可以匹配为止 next[i+1]=(T[i]==T[j])?j+1:0; //跳跃之后的当前母串S与子串T匹配，更新下一个位置的nxt数组值 } }第二种风格（严蔚敏版）：
void getNext(){ next[0]=next[1]=0; //赋初始值为0 int i=1,j=0; //从第二个位置开始 while(i<=m){ if(j==0||s[i]==s[j]) //如果当前j的值为0或者能够匹配成功 next[++i]=++j; //给下一个next[i]赋值 else j=next[j]; //否则指针j滑动（递减） } }