记录编号	460751	评测结果	AAW
题目名称	[POJ 3461] 乌力波	最终得分	66
用户昵称	Fisher.	是否通过	未通过
代码语言	C++	运行时间	1.533 s
提交时间	2017-10-18 10:16:48	内存使用	17.48 MiB

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define ll long long 
using namespace std;
const int maxn=1e6+10;
const int base=29;
const ll mo=1e7+7;
int t;
ll mi[maxn];
char a[maxn],b[maxn];
ll s[maxn];
ll md(ll x){return(x+mo)%mo;}
inline void cal(){
	int len1=strlen(a+1),len2=strlen(b+1);
	if(len1>len2){puts("0");return;}
	ll bi=0;
	for(int i=1;i<=len1;i++)bi=(bi*base+(ll)(a[i]-'A'))%mo;
	memset(s,0,sizeof(s));
	for(int i=1;i<=len2;i++)s[i]=(s[i-1]*base+(ll)(b[i]-'A'))%mo;
	int cnt=0;
	for(int i=1;i+len1-1<=len2;i++){
		ll out=md(s[i+len1-1]-md((s[i-1]*mi[len1])%mo));
		//cout<<out<<endl;
		if(out==bi)cnt++;
	}
	printf("%d\n",cnt);
}
int main(){
	freopen("oulipo.in","r",stdin);
	freopen("oulipo.out","w",stdout);
	scanf("%d",&t);
	mi[0]=1;
	for(int i=1;i<=1e4;i++)mi[i]=(mi[i-1]*base)%mo;
	while(t--){
		scanf("%s%s",a+1,b+1);
		cal();
	}
	return 0;
}