Oulipo

题意:

查找一个字符串在另一个字符串中出现的次数.

Sample Input
3
BAPC
BAPC
AZA
AZAZAZA
VERDI
AVERDXIVYERDIAN
Sample Output
1
3
0

sol：字符hash或KMP。

程序代码1：字符hash，取mod。

 1 #include<bits/stdc++.h>
 2 #define maxn 1e6+10 
 3 using namespace std;
 4 const int mod=19260817;
 5 long long  p[1000001],sum[1000001],num;
 6 int n;
 7 int b=193;
 8 char c1[100001],c2[1000001];
 9 
10 int main()
11 {
12     p[0]=1;
13     for(int i=1;i<=maxn;i++)// 求出b^i 
14          p[i]=p[i-1]*b%mod;
15     cin>>n;
16     while(n--)
17     {
18         int ans=0;
19         num=0;
20         sum[0]=0;
21         scanf("%s %s",c1+1,c2+1);
22         //查找c1串在c2中出现的次数 
23         int len1=strlen(c1+1);
24         int len2=strlen(c2+1);
25         for(int i=1;i<=len1;i++)//计算c1串的hash值 
26              num=((num*b%mod)+(c1[i]-'A'+1))%mod;
27         for(int i=1;i<=len2;i++)//将c2串的前若干位的值计算出来 
28              sum[i]=((sum[i-1]*b%mod)+(c2[i]-'A'+1))%mod;
29         for(int i=0;i<=len2-len1;i++)
30         //从c2的第0位开始，依次取len1的长度出来，与c1进行比较 
31              if(num==((sum[i+len1]-sum[i]*p[len1]%mod)+mod)%mod)
32                ans++;
33         printf("%d
",ans);
34     }
35     return 0;
36 }

程序代码2：字符hash，利用无符号整数自然溢出取模

 1 #include<bits/stdc++.h>
 2 #define maxn 1e6+10
 3 using namespace std;
 4 typedef unsigned long long ull;
 5 ull p[1000001],sum[1000001],Num;
 6 int n;
 7 int b=193;
 8 char c1[100001],c2[1000001];
 9 void read(int &x)
10 {
11     char ch; bool ok;
12     for(ok=0,ch=getchar(); !isdigit(ch); ch=getchar()) if(ch=='-') ok=1;
13     for(x=0; isdigit(ch); x=x*10+ch-'0',ch=getchar()); if(ok) x=-x;
14 }
15 int main()
16 {
17      
18     p[0]=1;
19     for(int i=1;i<=maxn;i++)
20          p[i]=p[i-1]*b;
21     read(n);
22     while(n--)
23     {
24         int ans=0;
25         Num=0;
26         sum[0]=0;
27         cin>>c1+1>>c2+1;
28         int len1=strlen(c1+1);
29         int len2=strlen(c2+1);
30         for(int i=1;i<=len1;i++)
31             Num=Num*b+ull(c1[i]-'A'+1);
32         for(int i=1;i<=len2;i++)
33             sum[i]=sum[i-1]*b+ull(c2[i]-'A'+1);
34         for(int i=0;i<=len2-len1;i++)
35              if(Num==sum[i+len1]-sum[i]*p[len1])
36                  ans++;
37         printf("%d
",ans);
38     }
39     return 0;
40 }

程序代码3：KMP

 1 #include<cstdio>
 2 #include<cstring>
 3 using namespace std;
 4 int pre[10010],t,n,m,ans;
 5 char a[10010],b[1000010];
 6  
 7 void get_next()
 8 {
 9     int j=0;
10     for (int i=1;i<n;i++)
11     {
12         while (j>0&&a[j+1]!=a[i+1]) j=pre[j];
13         if (a[j+1]==a[i+1]) j++;
14         pre[i+1]=j;
15     }
16 }
17  
18 void get_ans()
19 {
20     ans=0;
21     int j=0;
22     for (int i=0;i<m;i++)
23     {
24         while (j>0&&a[j+1]!=b[i+1]) j=pre[j];
25         if (a[j+1]==b[i+1]) j++;
26         if (j==n)
27         {
28             j=pre[j];//母串中的子串可重叠，j=pre[j]
               //j=0;注意，如果母串中的子串不可重叠，j=0
29             ans++;
30         }
31     }
32     printf("%d
",ans);
33 }
34  
35 int main(){
36     scanf("%d",&t);
37     while (t--){
38         memset(pre,0,sizeof(pre));
39         scanf("%s",a+1);
40         n=strlen(a+1);
41         scanf("%s",b+1);
42         m=strlen(b+1);
43         get_next();
44         get_ans();
45     }
46     return 0;
47 }