记录编号	455672	评测结果	AAA
题目名称	[POJ 3461] 乌力波	最终得分	100
用户昵称	Hallmeow	是否通过	通过
代码语言	C++	运行时间	0.611 s
提交时间	2017-10-02 18:01:24	内存使用	16.71 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<map>
using namespace std;
#define N 101000
#define pos(i,a,b) for(ULL i=(a);i<=(b);i++)
#define pos2(i,a,b) for(ULL i=(a);i>=(b);i--)
#define ULL unsigned long long
ULL n;
const ULL p=233;
char s[10100],s2[1010000];
ULL hash1[10100],hash2[1010000],xp[1001000];
void gethash1(){//处理出s1的hash 
	ULL len=strlen(s+1);
	hash1[len+1]=0;
	pos2(i,len,1){
		hash1[i]=(hash1[i+1]+(s[i]-'0'))*p;
	}
}
void gethash2(){
	ULL len=strlen(s2+1);
	hash2[len+1]=0;
	pos2(i,len,1){
		hash2[i]=(hash2[i+1]+(s2[i]-'0'))*p;
	}
	xp[0]=1;//处理出p的i次幂 
	pos(i,1,1001000){
		xp[i]=xp[i-1]*p;
	}
}
ULL get1(int i,int j){//取出下标为i~j的hash值 
	return hash1[i]-hash1[j+1]*xp[j+1-i];
}
ULL get2(int i,int j){
	return hash2[i]-hash2[j+1]*xp[j+1-i];
}
int t;
int main(){
	freopen("oulipo.in","r",stdin);
	freopen("oulipo.out","w",stdout);
	cin>>t;
	while(t--){
		scanf("%s%s",s+1,s2+1);
		gethash1();gethash2();
		int ans(0);
		int len1=strlen(s+1),len2=strlen(s2+1);
		pos(i,1,len2){
			if(i+len1-1>len2) break;
			if(get2(i,i+len1-1)==hash1[1]) ans++;
		} 
		cout<<ans<<endl;
	}
	return 0;
}