在网上有很多kmp算法的讲解，大概的框架讲的都还不错，但在next数组的讲解上，我觉得不是很清晰。
在学习KMP算法时，next数组的求解是它的精髓。
在博客中看了许多next数组的求法，推荐一篇 kmp算法.我觉得写的非常好。

理论基础

前缀：字符串A和B，A=B+S，S非空，则B为A的前缀
后缀：字符串A和B，A=S+B，S非空，则B为A的后缀
PMT值：前缀集合和后缀集合的交集中，最长元素的长度
prefix:每一个下标位置对应一个PMT值，组成的数组
next：prefix向右移一个下标位置，组成的next数组

部分匹配表的生成

在学习next数组之前，我们先来看一下PMT值组成的数组，也就是kmp算法的部分匹配表，通过PMT值我们就可以知道子字符串应该如何移动，而不用进行整个回溯。如下图字符串BCADBCABCABCD为主串，字符串BCADBCD为副串，将副串与主串进行匹配，搜寻副串在主串中的位置。我们使用i来表示主串当前比对字符的位置，用j来表示副串当前比对字符的位置。我们从子字符串的j为0位置开始与主字符串进行一一比对，一直到子字符串的j为5位置子字符串和主字符串都是匹配的，在比对子字符串的6位置时即红色位置对应的位置时，不匹配。按照正常的思路，我们需要回溯，将i从6回溯到1的位置，将j从6返回到0的位置，再次进行匹配。将搜索词整个后移一位，再从头逐个比较。这样做虽然可行，但是效率很差，因为你要把"搜索位置"移到已经比较过的位置，重比一遍。

但是，我们在图中可以看出，当字符A与D不匹配时，你其实知道前面六个字符是"BCADBC"。即我们已经知道主串位置4前面不能与字串进行匹配，所以不用进行比对。而子串位置6前的BC和字串01位置的BC有重复，也不用与主串进行比对，所以我们可以将字串比对字符的位置移到2位置,即移到此元素对应的next值位置，与主串继续进行匹配。KMP算法的想法是，设法利用这个已知信息，不要把"搜索位置"移回已经比较过的位置，继续把它向后移，这样就提高了效率,即利用next数组，来提高匹配速度。

模式串	B	C	A	D	B	C	D
PMT值	0	0	0	0	1	2	0
next值	-1	0	0	0	0	1	2

PMT值的生成

下标5：ABCABC
下标5的前缀集合：A、AB、ABC、ABCA、ABCAB
下标5的后缀集合：C、BC、ABC、CABC、BCABC
最长交集元素长度：3（ABC）

下标6：ABCABCD
下标5的前缀集合：A、AB、ABC、ABCA、ABCAB、ABCABC
下标5的后缀集合：D、CD、BCD、ABCD、CABCD、BCABCD
最长交集元素长度：3（ABC）

从下标最长交集元素长度，可推出PMT值，将PMT值右移一位，即可得到next数组。

next数组的生成

next数组的生成与上面经过PMT数组右移一位生成的相同。下面讲解next数组怎末生成
next数组的生成，也就是子字符串与自己副本进行匹配对比的过程。
我们将上面字符串叫做子字符串本体，下面字符串作为子字符串副本

先将子字符串复制一份，复制子字符串后移一位，进行按字符匹配。
index0的位置，pmt为0，next的值为-1，也就是i=0，对应的j值，一般next数组第一位的值都是-1。

当index为1:将i和j同时加一，此时子串字符B和复制字串字符A失配，next[1]值为当前j值，即next[1]值为0，j下标设置为下标0的next值-1，即j=next[0],j=-1代表着复制字串要向后移一位。

index2:当 j=-1时,将i和j同时增加，即相当i+1，j=0,相当于复制字串右移一位，继续与字串继续进行比对，此时又失配，next[2]=j=0。而j=next[j]=-1,复制字串将将继续后移。

index3时: j=-1时,将i和j同时增加，即相当i+1，j=0,相当于复制字串右移一位，继续与字串继续进行比对，此时子串本体对应字符和副本对应字符匹配，next[3]=j=0。继续匹配下一位。
index4时：将i和j同时增加，i=4,j=1,本体与副本继续对比，此时子串本体对应字符和副本对应字符适配，next[4]=j=1继续匹配下一位。
index5时：将i和j同时增加，i=6,j=2,本体与副本继续对比，此时子串本体对应字符和副本对应字符适配，next[5]=j=2继续匹配下一位。

index6时：将i和j同时增加，i=6,j=2,本体与副本继续对比，此时子串本体对应字符和副本对应字符失配，next[5]=j=3，j=next[j]=0。按照此思路一直求解下去，自此next数组已经求解完毕。

代码实现

void getNext(char pattern[],int next[]){next[0]=-1;int i=0,j=-1;int pat_leng = strlen(pattern);while(i<pat_leng){if(j==-1) {i++;j++;} else if(pattern[i] == pattern[j]){i++;j++;next[i]=j;} else{j=next[j];}}
}

主要讲解的是next数组求解的代码，按照上面图片的思路，如果j==-1的话，i和j同时加一，然后下一次循环判断是否相等，如果适配，即相等，就i和j同时加一，检查下一位是否也相等。如果失配，即不相等的话，则将next[j]的值赋给j，继续进入循环。

int search(char str[],char pattern[],int next[]){int i=0,j=0;int str_length = strlen(str);int pattern_length = strlen(pattern);while(i<str_length && j<pattern_length){if( j==-1 || str[i] == pattern[j]){++i;++j;} else j=next[j];}if(j == pattern_length)return i-j;else return -1;
}

int main()
{char pattern[] ={"ABCABCD"};char str[]={"ABCABCCABCABCD"};int next[20]={0};getNext(pattern,next);printf("%d",search(str,pattern,next));return 0;
}