P3375 【模板】KMP字符串匹配

 1 ////KMP模式匹配 
 2 ////a、b字符串下标均从1开始 
 3 #include<bits/stdc++.h>
 4 using namespace std;
 5 const int maxn=1000005;
 6 int lena,lenb; 
 7 char a[maxn],b[maxn];
 8 int Next[maxn];//注意这里为int 
 9 inline void init()//预处理Next数组 
10 {
11     for(int i=1,j=0;i<lenb;++i)//Next[1]=0,故i从1开始,到lenb-1结束 
12     {
13         while(j>0&&b[j+1]!=b[i+1]) j=Next[j];//若b[i+1]!=b[j+1]（无法匹配） 尝试减小j的值 
14         if(b[i+1]==b[j+1]) ++j;//能继续匹配 j的值+1 
15         Next[i+1]=j;//每次处理Next[i+1] 
16     }
17 }
18 inline void KMP()
19 {
20     for(int i=0,j=0;i<lena;++i)
21     {
22         while(j>0&&b[j+1]!=a[i+1]) j=Next[j];//若不能继续匹配 减小j的值 
23         if(b[j+1]==a[i+1]) ++j; //能继续匹配 j的值+1 
24         if(j==lenb) {printf("%d
",i+1-lenb+1);j=Next[j];}
25         //匹配成功 此时b[j]=a[i+1] (i+1)-lenb+1即为b串首位置 缩小j以寻找下一处匹配 
26     }
27 }
28 int main()
29 {
30     scanf("%s%s",a+1,b+1);
31     lena=strlen(a+1),lenb=strlen(b+1);
32     init();
33     KMP();
34     for(int i=1;i<=lenb;i++) printf("%d ",Next[i]);//输出Next数组 
35     return 0;
36 }