题意:
查找一个字符串在另一个字符串中出现的次数.
Sample Input
3
BAPC
BAPC
AZA
AZAZAZA
VERDI
AVERDXIVYERDIAN
Sample Output
1
3
0
Sol:典型的字符hash.
Std1:取mod
#include<bits/stdc++.h> #define maxn 1e6+10 using namespace std; const int mod=19260817; long long p[1000001],sum[1000001],num; int n; int b=193; char c1[100001],c2[1000001]; int main() { p[0]=1; for(int i=1;i<=maxn;i++)// 求出b^i p[i]=p[i-1]*b%mod; cin>>n; while(n--) { int ans=0; num=0; sum[0]=0; scanf("%s %s",c1+1,c2+1); //查找c1串在c2中出现的次数 int len1=strlen(c1+1); int len2=strlen(c2+1); for(int i=1;i<=len1;i++)//计算c1串的hash值 num=((num*b%mod)+(c1[i]-‘A‘+1))%mod; for(int i=1;i<=len2;i++)//将c2串的前若干位的值计算出来 sum[i]=((sum[i-1]*b%mod)+(c2[i]-‘A‘+1))%mod; for(int i=0;i<=len2-len1;i++) if(num==((sum[i+len1]-sum[i]*p[len1]%mod)+mod)%mod) ans++; printf("%d\n",ans); } return 0; }
Std2:用无符号整数计算hash值，用自然溢出求掉求模运算
#include<bits/stdc++.h>
#define maxn 1e6+10
using namespace std;
typedef unsigned long long ull;
ull p[1000001],sum[1000001],Num;
int n;
int b=193;
char c1[100001],c2[1000001];
void read(int &x)
{
char ch; bool ok;
for(ok=0,ch=getchar(); !isdigit(ch); ch=getchar()) if(ch==‘-‘) ok=1;
for(x=0; isdigit(ch); x=x*10+ch-‘0‘,ch=getchar()); if(ok) x=-x;
}
int main()
{
p[0]=1;
for(int i=1;i<=maxn;i++)
p[i]=p[i-1]*b;
read(n);
while(n--)
{
int ans=0;
Num=0;
sum[0]=0;
cin>>c1+1>>c2+1;
int len1=strlen(c1+1);
int len2=strlen(c2+1);
for(int i=1;i<=len1;i++)
Num=Num*b+ull(c1[i]-‘A‘+1);
for(int i=1;i<=len2;i++)
sum[i]=sum[i-1]*b+ull(c2[i]-‘A‘+1);
for(int i=0;i<=len2-len1;i++)
if(Num==sum[i+len1]-sum[i]*p[len1])
ans++;
printf("%d\n",ans);
}
return 0;
}
类似的习题有Poj2406 Power String,此题还可以用Kmp算法来做
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
using namespace std;
typedef unsigned long long LL;
const LL base=131;
const int N=1000010;
int n;
LL power[N],sum[N];
bool check(LL v,int k) //判断s[1]~s[k]是否是循环节
{
for(register int i=1;i<=n;i+=k) //一路推过去每k位都应该值等于v
{
if(v!=sum[i+k-1]-sum[i-1]*power[k])
return 0;
}
return 1;
}
int main()
{
power[0]=1;
for(register int i=1;i<=N-10;++i) //hash准备工作
power[i]=power[i-1]*base;
char s[N];
while(scanf("%s",s+1))
{
if(s[1]==‘.‘)break;
n=strlen(s+1);
sum[0]=0;
for(register int i=1;i<=n;++i)
sum[i]=sum[i-1]*base+LL(s[i]);
for(register int i=1;i<=n;++i)
{
if(n%i) //循环节长度i，应为n的约数
continue;
LL expect=sum[i];
if(check(expect,i))
{
printf("%d\n",n/i);
break;
}
}
}
return 0;
}
原文：https://www.cnblogs.com/cutemush/p/12295936.html