字符串哈希板子

字符串哈希板子

http://oj.daimayuan.top/course/7/problem/485
单哈希

# include<bits/stdc++.h>

using namespace std;
const int N = 2e5+10;
const int p = 9999971,base = 101;

int n,m;
char a[N],b[N]; //字符串a,b
int ha[N],hb[N],c[N]; //ha是a的哈希函数，hb是b的哈希函数
                      //c[i] = base的i次方

int main()
{
	cin>>n>>m;
	scanf("%s%s",a+1,b+1);
	c[0] = 1;
	for(int i=1;i<=n;i++) c[i] = c[i-1]*base%p;
	for(int i=1;i<=n;i++) ha[i] = ( ha[i-1]*base+(a[i]-'a'))%p;
	for(int i=1;i<=m;i++) hb[i] = ( hb[i-1]*base+(b[i]-'a'))%p;
	int ans = 0;
	for(int i=1;i+m-1<=n;i++) 
	{
		if( (ha[i+m-1]-1ll*ha[i-1]*c[m]%p+p) % p == hb[m] ) ++ans;
	}
	cout<<ans<<endl;
	return 0;
}

双哈希

# include<bits/stdc++.h>

using namespace std;
const int N = 2e5+10;
const int p1 = 9999971,base1 = 101;
const int p2 = 9999973,base2 = 137;
int n,m;
char a[N],b[N];
int ha1[N],hb1[N],c1[N],c2[N],ha2[N],hb2[N];

int main()
{
	cin>>n>>m;
	scanf("%s%s",a+1,b+1);
	c1[0] = c2[0] = 1;
	for(int i=1;i<=n;i++) c1[i] = c1[i-1]*base1%p1;
	for(int i=1;i<=n;i++) c2[i] = c2[i-1]*base2%p2;
	for(int i=1;i<=n;i++) 
	{
		ha1[i] = ( ha1[i-1]*base1+(a[i]-'a'))%p1;
		ha2[i] = ( ha2[i-1]*base2+(a[i]-'a'))%p2;
	}
	for(int i=1;i<=m;i++) 
	{
		hb1[i] = ( hb1[i-1]*base1+(b[i]-'a'))%p1;
		hb2[i] = ( hb2[i-1]*base2+(b[i]-'a'))%p2;
	}
	int ans = 0;
	for(int i=1;i+m-1<=n;i++) 
	{
		if( (ha1[i+m-1]-1ll*ha1[i-1]*c1[m]%p1+p1) % p1 == hb1[m] && (ha2[i+m-1]-1ll*ha2[i-1]*c2[m]%p2+p2) % p2 == hb2[m] ) ++ans;
	}
	cout<<ans<<endl;
	return 0;
}

在算竞中，单哈希或者自然溢出都是会被卡掉的，所以写的话就写双哈希就行