【模板】字符串哈希

取进制数为131，每次(O(N))时间预处理出幂次和母串的滚动哈希值。

代码如下

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e6+10;
const int base=131;

char s1[maxn],s2[maxn];
unsigned long long power[maxn],tot,h[maxn],l1,l2,ans;

int main(){
	scanf("%s%s",s1+1,s2+1);
	l1=strlen(s1+1),l2=strlen(s2+1);

	power[0]=1;
	for(int i=1;i<=l1;i++)power[i]=power[i-1]*base;
	for(int i=1;i<=l1;i++)h[i]=h[i-1]*base+s1[i]-'A';//滚动哈希
	for(int i=1;i<=l2;i++)tot=tot*base+s2[i]-'A';

	for(int i=l2;i<=l1;i++)
		if(tot==h[i]-h[i-l2]*power[l2])//子串哈希值
			++ans;
	printf("%d
",ans);
	return 0;
}