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);
	}
}