记录编号	248067	评测结果	A
题目名称	[POJ 3461] 乌力波	最终得分	100
用户昵称	liu_runda	是否通过	通过
代码语言	C++	运行时间	0.881 s
提交时间	2016-04-10 07:05:20	内存使用	1.48 MiB

#include<cstdio>
#include<cstring>
#include<cstdlib>
typedef unsigned long long LL;
char s1[1000000],s2[10005];
const LL mod1=89999981,mod2=333331,base=177777;
LL pow[10005];
LL pow2[10005];
LL pow3[10005];
LL gethash(char s[],int len){
	LL hash=0;
	for(int i=0;i<len;++i){
		hash=hash*base+s[i]-'A';
		hash%=mod1;
	}
	return hash;
}
LL updatehash(LL oldhash,char s[],int pos,int len){
	return ((oldhash+mod1-(s[pos-len]-'A')*pow[len-1]%mod1)*base+s[pos]-'A')%mod1;
}

LL gethash2(char s[],int len){
	LL hash=0;
	for(int i=0;i<len;++i){
		hash=hash*base+s[i]-'A';
		hash%=mod2;
	}
	return hash;
}
LL updatehash2(LL oldhash,char s[],int pos,int len){
	return ((oldhash+mod2-(s[pos-len]-'A')*pow2[len-1]%mod2)*base+s[pos]-'A')%mod2;
}
int main(){
	freopen("oulipo.in","r",stdin);
	freopen("oulipo.out","w",stdout);
	int t;scanf("%d",&t);
	pow[0]=1;
	for(int i=1;i<=10000;++i){
		pow[i]=(pow[i-1]*base)%mod1;
	}
	pow2[0]=1;
	for(int i=1;i<=10000;++i){
		pow2[i]=(pow2[i-1]*base)%mod2;
	}
	while(t--){
		scanf("%s %s",s2,s1);
		int len1=strlen(s1),len2=strlen(s2);
		int hashw=gethash(s2,len2),hashp=gethash(s1,len2);
		int hashw2=gethash2(s2,len2),hashp2=gethash2(s1,len2);
		int ans=0;
	//	printf("%d %d\n",hashw,hashp);
		if(hashw==hashp&&hashw2==hashp2)ans++;
		for(int i=len2;i<len1;++i){
			hashp=updatehash(hashp,s1,i,len2);
			hashp2=updatehash2(hashp2,s1,i,len2);
		//	hashp3=updatehash3(hashp3,s1,i,len2);
		//	printf("%d\n",hashp);
			if(hashp==hashw&&hashp2==hashw2)ans++;
		}
		printf("%d\n",ans);
	}
	fclose(stdin);fclose(stdout);
	return 0;
}