字符串hash

https://blog.csdn.net/pengwill97/article/details/80879387

https://blog.csdn.net/chaiwenjun000/article/details/71079819

AC代码

#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
typedef unsigned long long ull;
const int maxn=1e6+;
const int base=; //base，基数

ull power[maxn]; //存储b^n
void init()
{
power[]=; //base^0=1
for(int i=; i<maxn; i++)
power[i]=power[i-]*base; //对ull取模
}

char s1[maxn],s2[maxn];
ull Hash[maxn]; //记录主串哈希值的数组

int main()
{
init();
int T;
cin>>T;
while(T--)
{
scanf("%s%s",s1+,s2+); //从第一位开始输入
int n=strlen(s1+),m=strlen(s2+);
Hash[]=; //记录主串哈希值的数组
for(int i=; i<=m; i++) //计算主串的滚动Hash值
Hash[i]=Hash[i-]*base+(ull)(s2[i]-'A'+);
ull s=;
for(int i=; i<=n; i++) //计算匹配串的Hash值
s=s*base+(ull)(s1[i]-'A'+);
int ans=;
for(int i=; i<=m-n; i++)
if(s==Hash[i+n]-Hash[i]*power[n])
ans++;
printf("%d\n",ans);
}
return ;
}