关键概念：
1.最大相同前后缀
abab->ab;
abcdabc->abc;
ababa->aba而不是ababa;
2.next数组的含义及其求法
next[i]=j, 意味着模式串 i 位置之前（不包括i位置）的最大相同前后缀，前缀末尾的下一位是 j
比如模式串：abab; 对应的next[]={-1，0，0，1}，
i=0时，next[0]用-1特别标识；
i=1时，next[1]=0，即：ab,看成“a|b”,b前面最长相同前后缀不存在，前缀末尾的下一位自然应该设置为第一个字符，即a所在的位置0
i=2时，next[2]=0，即：aba, 看成“ab|a”理由同上，前缀末尾下一位只好设置为0
i=3时，next[3]=1，即：abab,看成“aba|b”，这时最长相同前后缀是a,前缀下一位就是b的位置1
要点：已知的next[i]=j，根据此时模式串 p[i] 和 p[j] 是否相等来得出 next[i+1] 等于什么。（最重要）
这里有两个next数组的递推法则：
1.p[i]=p[j]，则：next[++i]=++j;
2.p[i]!=p[j]，则：令 j=next[j]，用新的p[j]与p[i]比较。
1 #include <stdio.h> 2 #include <stdlib.h> 3 #include <string.h> 4 5 void getnext(char a[],int next[]){//根据已知的next[i]=j，根据此时模式串p[i]和p[j]是否相等来得出next[i+1]等于什么 6 int n = strlen(a); 7 int i=0,j=-1; 8 next[0] = -1; 9 while(i < n){//n是数组a有效数据的长度 10 if(j==-1 || a[i]==a[j]){//j==-1一方面使得i=0，j=-1时进入next赋值语句使得next[1]=0 11 next[++i]=++j; 12 } 13 else j = next[j]; 14 } 15 } 16 void NewGetNext(char p[],int next[]){//改进版求next数组方法 17 int n = strlen(p); 18 int i=0,j=-1; 19 next[0] = -1; 20 while(i < n){//n是数组a有效数据的长度 21 if(j==-1 || p[i]==p[j]){ 22 // next[++i]=++j;未改进的 23 i++,j++; 24 //改进后的： 25 if(p[j] != p[i]) 26 next[i]=j; 27 else//如果p[j]==p[i]，那么直接next[i]=j就会导致下一次模式串j位置开始的匹配 与 目标串i位置再出不匹配 28 next[i]=next[j]; 29 //改进后的： 30 } 31 else j = next[j]; 32 } 33 } 34 35 int KMP(char s[], char p[], int next[]){ 36 int i=0; 37 int j=0; 38 int slen=strlen(s); 39 int plen=strlen(p); 40 while(i<slen && j<plen){ 41 if(j==-1 || s[i]==p[j]){ 42 i++,j++; 43 } 44 else{ 45 j = next[j];//匹配失败(j!=-1 且 s[i]!=p[j]),则i不变，j变动，用变化后的j重新和i匹配 46 } 47 } 48 if(j==plen) 49 return i-j;//返回成功匹配（第一次）从哪里开始的位置 50 //比如s="123abab",p="abab",最后i指向最后的b,而j也指向最后的b,7-4=3,s[3]即是开始位置 51 else 52 return -1; 53 } 54 void print(int a[],int len)//打印数组的函数 55 { 56 printf("开始打印\n"); 57 for(int i=0;i<len;i++) 58 printf("%d\t", a[i]); 59 printf("\n结束打印\n"); 60 } 61 int main(int argc, char const *argv[]) 62 { 63 char p[]="abacdababc"; 64 char s[]="123baababaab zxklchakk"; 65 int n= sizeof(p)/sizeof(char)-1; 66 int next[n]; 67 //以下为测试语句 68 printf("getnext:\n" ); 69 getnext(p,next); 70 print(next,n); 71 printf("\nNewgetnext:\n"); 72 for(int i=0;i<sizeof(next)/sizeof(int)-1;i++) next[i]=0; 73 NewGetNext(p,next); 74 print(next,n); 75 return 0; 76 }