1 void makeNext(const char P[],int next[]) 2 { 3     int q,k;//q:模版字符串下标；k:最大前后缀长度 4     int m = strlen(P);//模版字符串长度 5     next[0] = 0;//模版字符串的第一个字符的最大前后缀长度为0 6     for (q = 1,k = 0; q < m; ++q)//for循环，从第二个字符开始，依次计算每一个字符对应的next值 7     { 8         while(k > 0 && P[q] != P[k])//递归的求出P[0]···P[q]的最大的相同的前后缀长度k 9             k = next[k-1];          //不理解没关系看下面的分析，这个while循环是整段代码的精髓所在，确实不好理解  10         if (P[q] == P[k])//如果相等，那么最大相同前后缀长度加111         {12             k++;13         }14         next[q] = k;15     }16 }

 1 #include<stdio.h> 2 #include<string.h> 3 void makeNext(const char P[],int next[]) 4 { 5     int q,k; 6     int m = strlen(P); 7     next[0] = 0; 8     for (q = 1,k = 0; q < m; ++q) 9     {10         while(k > 0 && P[q] != P[k])11             k = next[k-1];12         if (P[q] == P[k])13         {14             k++;15         }16         next[q] = k;17     }18 }19 20 int kmp(const char T[],const char P[],int next[])21 {22     int n,m;23     int i,q;24     n = strlen(T);25     m = strlen(P);26     makeNext(P,next);27     for (i = 0,q = 0; i < n; ++i)28     {29         while(q > 0 && P[q] != T[i])30             q = next[q-1];31         if (P[q] == T[i])32         {33             q++;34         }35         if (q == m)36         {37             printf("Pattern occurs with shift:%d\n",(i-m+1));38         }39     }    40 }41 42 int main()43 {44     int i;45     int next[100]={0};46     char T[20], P[20];47     scanf("%s%s", T,P);48     49     printf("%s\n",T);50     printf("%s\n",P );51     // makeNext(P,next);52     kmp(T,P,next);53     for (i = 0; i < strlen(P); ++i)54     {55         printf("%d ",next[i]);56     }57     printf("\n");58 59     return 0;60 }