KMP算法用于字符串匹配
1 /*KMP*/ 2 #include<stdio.h> 3 #include<string.h> 4 char s1[1000005],s2[1005];//s1 为待匹配串，s2为模板串 5 int nxt[1005],n,m; 6 int main() 7 { 8 scanf("%s%s",s1+1,s2+1); 9 n = strlen(s1+1); m = strlen(s2+1); 10 nxt[1] = 0; int i,k = 0; 11 for(i=2;i<=m;i++) 12 { 13 while(k>0&&s2[k+1]!=s2[i]) k = nxt[k]; 14 if(s2[k+1]==s2[i]) k++; 15 nxt[i] = k; 16 } 17 k = 0; 18 for(i=1;i<=n;i++) 19 { 20 while(k>0&&s2[k+1]!=s1[i]) k = nxt[k]; 21 if(s2[k+1]==s1[i]) k++; 22 if(k==m) printf("%d ",i-m+1),k=nxt[k]; 23 } 24 for(i=1;i<=m;i++) printf("%d ",nxt[i]); 25 return 0; 26 }