https://loj.ac/problem/103
题目描述
给定一个字符串(A)和一个字符串(B)，求(B)在(A)中的出现次数。(A)和(B)中的字符均为英语大写字母或小写字母。
思路
显然这是道字符串匹配题，我们可以用(KMP)求解。但这里我主要想介绍一种更简单的方法：字符串(Hash)。我们去一个基数(b)，把字符串看做(b)进制的数。而为了尽快求出一定长度的字符串的(Hash)值，我们可以用滚动(Hash)。这一过程可以用递推完成：(H(C，k+1)=H(C，k)*b + c_{k+1})。因此我们可以求出从通过以下式子求出从(k)开始长(n)的字符串(Hash)值：
[H(C’)=H(C，k+n)-H(C，k)*b^n。
]
那么做一遍就行了。
代码
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const ull b=131;
char s1[1000005],s2[1000005];
ull power[1000005],sum[1000005];
int main()
{
scanf(" %s %s",s1+1,s2+1);
power[0]=1;
for(int i=1;i<1000000;i++)
power[i]=power[i-1]*b;
int m=strlen(s1+1),n=strlen(s2+1);
for(int i=1;i<=m;i++)
sum[i]=sum[i-1]*b+s1[i];
ull s=0,ans=0;
for(int i=1;i<=n;i++)
s=s*b+s2[i];
for(int i=0;i<=m-n;i++)
if(s==sum[i+n]-sum[i]*power[n])ans++;
printf("%lld",ans);
return 0;
}