- 理论基础
- 部分匹配表的生成
- PMT值的生成
- next数组的生成
- 代码实现
在网上有很多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位置副字符串和主字符串都是匹配的，在比对副字符串的j=6位置时即红色位置对应的位置时，不匹配。
按照正常的思路，我们需要回溯，将i从6回溯到1的位置，将j从6返回到0的位置，再次进行匹配。将副字符串整个后移一位，再从头逐个比较。这样做虽然可行，但是效率很差，因为你要把"搜索位置"移到已经比较过的位置，重比一遍。
但是，我们在图中可以看出，当字符A与D不匹配时，你其实知道前面六个字符是"BCADBC"。即我们已经知道主串位置4前面不能与副串进行匹配，所以不用进行比对。而主串位置6前的BC两个字符与副串01位置的BC两个字符有重复，也不用与主串进行比对，所以我们可以将副串比对字符的位置移到2位置,即移到j=6元素对应的next值位置(下面又此字符串的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 |
下标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=5,j=2,本体与副本继续对比，此时子串本体对应字符和副本对应字符适配，next[5]=j=2继续匹配下一位。
index6时：将i和j同时增加，i=6,j=3,本体与副本继续对比，此时子串本体对应字符和副本对应字符失配，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
主要讲解的是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
搜索代码和暴力搜索字符串的思路基本一样，只不过将回退的代码换成了赋值next数组。
int main()
{
char pattern[] ={"ABCABCD"};
char str[]={"ABCABCCABCABCD"};
int next[20]={0};
getNext(pattern,next);
printf("%d",search(str,pattern,next));
return 0;
}
