POJ3461 Oulipo

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 using namespace std;
 5 const int size=1000020,p=131;
 6 typedef unsigned long long ULL;
 7 ULL f[size],key[size]; 
 8 int T;
 9 char tmp1[size],tmp2[size];
10 int main(){
11     f[0]=1;
12     for(int i=1;i<=size;++i) f[i]=f[i-1]*p;
13     scanf("%d",&T);
14     while(T--){
15         scanf("%s%s",tmp1+1,tmp2+1);
16         int len1=strlen(tmp1+1),len2=strlen(tmp2+1);
17         for(int i=1;i<=len2;++i) key[i]=key[i-1]*p+(ULL)(tmp2[i]);
18         ULL key_tmp1=0;int ans=0;
19         for(int i=1;i<=len1;++i) key_tmp1=key_tmp1*p+(ULL)tmp1[i];
20         for(int i=0;i<=len2-len1;++i) if(key[i+len1]-key[i]*f[len1]==key_tmp1) ++ans;
21         printf("%d
",ans);
22     }
23     return 0;
24 }

 1 //KMP
 2 #include<iostream>
 3 #include<cstdio>
 4 #include<stack>
 5 #include<cstring>
 6 #include<algorithm>
 7 #include<vector>
 8 using namespace std;
 9 const int size=1000005;
10 char a[size],b[size];
11 int Nex[size],lena,lenb,T,ans;
12 void init(char *s){
13     for(int i=2,j=0;i<=lenb;++i){
14         while(j>0&&s[j+1]!=s[i]) j=Nex[j];
15         if(s[j+1]==s[i]) ++j;
16         Nex[i]=j;
17     }
18 }
19 void kmp(char *a,char *b){
20     memset(Nex,0,sizeof(Nex));
21     init(b);
22     for(int i=1,j=0;a[i];++i){
23         while(j&&a[i]!=b[j+1]) j=Nex[j];
24         if(a[i]==b[j+1]) ++j;
25         if(j==lenb) ++ans,j=Nex[j];
26     }
27 }
28 int main(){
29     scanf("%d",&T);
30     while(T--){
31         ans=0;
32         scanf("%s%s",b+1,a+1);
33         lena=strlen(a+1),lenb=strlen(b+1);
34         kmp(a,b);
35         printf("%d
",ans);
36     }
37     return 0;
38 }