#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
typedef long long LL;
const int maxn=1000010;
const LL mod=912837417;
const LL Base=1234567;
LL base[maxn],hash[maxn];
LL hashP;
char T[maxn],P[maxn];
LL lenT,lenP;
LL tot;
LL ANS;
inline LL query(LL l,LL r){
	LL ans=(hash[r]-hash[l-1]*base[r-l+1])%mod;
	if(ans<0) ans+=mod;
	return ans;
}
int main(){
	scanf("%d",&tot);
	for(LL i=1;i<=tot;i++){
		ANS=0; hashP=0;
		memset(base,0,sizeof(base)); memset(hash,0,sizeof(hash));
		memset(T,0,sizeof(T)); memset(P,0,sizeof(P));
		scanf("%s%s",P+1,T+1);
		lenT=strlen(T+1); lenP=strlen(P+1);
		base[0]=1;
		for(LL i=1;i<=lenT;i++){
			base[i]=(base[i-1]*Base)%mod;
			hash[i]=(hash[i-1]*Base+(LL)(T[i]-'A'+1))%mod;
			if(i<=lenP) hashP=(hashP*Base+LL(P[i]-'A'+1))%mod;
		}
		for(LL i=1;i<=lenT-lenP+1;i++){
			LL to=i+lenP-1;
			LL now=query(i,to);
			if(now==hashP) ANS++;
		}
		cout<<ANS<<endl;
	}
	return 0;
}

• Re:哈希为什么超时，是我写错了吗？ (11) ccc000111 2017-06-11 14:55:09