1 #include<cstring> 2 #include<algorithm> 3 #include<cstdio> 4 using namespace std; 5 const int maxn=1e6; 6 char a[maxn+50],b[maxn+50]; 7 int f[maxn+50]; 8 int len1,len2,t; 9 int main()10 {11     scanf("%d\n",&t);12     while(t)13     {14         --t;15         scanf("%s%s",b,a);//a是母串 b是匹配串16         len1=strlen(a),len2=strlen(b);17         memset(f,0,sizeof(f));18         f[0]=f[1]=0;//f[i]失配函数19         for(int i=1;i<len2;++i)20         {21             int j=f[i];22             while(j&&b[i]!=b[j]) j=f[j];23             if(b[i]==b[j]) f[i+1]=j+1;else f[i+1]=0;24         }25         int j=0,ans=0;26         for(int i=0;i<len1;++i)27         {28             while(j&&a[i]!=b[j]) j=f[j];29             if(b[j]==a[i])  ++j;30             if(j==len2) ++ans;31         }32         printf("%d\n",ans);33     }34     return 0;35 }

 1 #include<cstring> 2 #include<algorithm> 3 #include<cstdio> 4 using namespace std; 5 const int maxn=1e6; 6 char S[maxn+50],T[maxn+50];//S是母串，T是子串 7 int len1,len2; 8 int next[maxn+50],extend[maxn+50];//extend[i]表示S[i..len1-1]和T的最长公共前缀的长度，next[i]表示T[i..len2-1]和T的最长公共前缀的长度 9 void getnext()10 {11     next[0]=len2;12     int j=0;13     while(j+1<len2&&T[j]==T[j+1]) ++j;14     next[1]=j;15     int k=1;16     for(int i=2;i<len2;++i)17     {18         int p=k+next[k]-1,l=next[i-k];19         if(i+l<p+1) next[i]=l;20         else21         {22             j=max(p-i+1,0);23             while(i+j<len2&&T[i+j]==T[j]) ++j;24             k=i;25         }26     }27 }28 void ekmp()29 {30     int j=0;31     while(j<len1&&j<len2&&S[j]==T[j]) ++j;32     extend[0]=j;33     int k=0;34     for(int i=1;i<len1;++i)35     {36         int p=k+extend[k]-1,l=next[i-k];//p表示到达的最远位置，k是对应最远位置的i37         if(i+l<p+1) extend[i]=l;38         else39         {40             j=max(p-i+1,0);41             while(i+j<len1&&j<len2&&S[i+j]==T[j]) ++j;42             extend[i]=j;43             k=i;44         }45     }46 }47 int main()48 {49     scanf("%s%s",S,T);50     len1=strlen(S),len2=strlen(T);51     getnext();52     ekmp();53     for(int i=0;i<len1;++i) printf("%d ",extend[i]);54     return 0;55 }