poj3461 Oulipo(字符串哈希)

poj3461

http://poj.org/problem?id=3461

字符串hash模板题。给你2个串s1,s2(长度n,m),问s1在s2中出现几次。

字符串hash步骤：

1、  取一个质数p

我一般取999983。据说应该再模一个q(一般取1e9+7),但模了有时会超时。于是我一般不模q，让它自然溢出。但有一种数据专门卡这种自然溢出，于是我写一种假的双hash：将q作为另一个p，再做一遍。

2、  预处理p^(1~m)

3、  类似前缀和方式求出s2的hash[i]：h[i]=h[i-1]*p+s2[i]

4、  求出s1的哈希值s

5、  求出s2长度为n的子串的哈希值h[i+n]-h[i]*(p^n),并与s比较

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#define p 999983
#define q 1000000007
#define ull unsigned long long
using namespace std;

ull h[1000001],h2[1000001],po[1000001],qo[1000001];
char s1[10001],s2[1000001];
int main()
{
	int t;
	scanf("%d",&t);
	po[0]=1;
	qo[0]=1;
	for(int i=1;i<1000000;++i)
		po[i]=po[i-1]*p,
		qo[i]=qo[i-1]*q;
	while(t--){
		scanf("%s%s",s1+1,s2+1);
		int n=strlen(s1+1),m=strlen(s2+1);
		for(int i=1;i<=m;++i){
			h[i]=h[i-1]*p+s2[i],
			h2[i]=h2[i-1]*q+s2[i];
			//cout<<h[i]<<endl;
		}
		ull s=0,s2=0;
		for(int i=1;i<=n;++i) s=s*p+s1[i],s2=s2*q+s1[i];
		//cout<<"s "<<s<<endl;
		int ans=0;
		for(int i=0;i<=m-n;++i){
			if(s==h[i+n]-h[i]*po[n]&&s2==h2[i+n]-h2[i]*qo[n]) ++ans;
			//cout<<((ll)h[i+n]+(ll)q*q-(ll)h[i]*po[n])%q<<endl;
		}
		printf("%d\n",ans);
	}
}