首页 > 代码库 > 【模板】KMP算法
【模板】KMP算法
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\n",i-m+1),k=nxt[k]; 23 } 24 for(i=1;i<=m;i++) printf("%d ",nxt[i]); 25 return 0; 26 }
【模板】KMP算法
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。