记录编号	581732	评测结果	AAA
题目名称	[POJ 3461] 乌力波	最终得分	100
用户昵称	┭┮﹏┭┮	是否通过	通过
代码语言	C++	运行时间	0.829 s
提交时间	2023-08-11 22:04:12	内存使用	20.99 MiB

#include <bits/stdc++.h> 
using namespace std;
typedef unsigned long long ll;
const ll P = 1e9+7,N = 1e6+10;
int T,ans;
ll h,ha[N],pw[N];
string s1,s2;
void first_(){
	h = 0;ans = 0;
	memset(ha,0,sizeof(ha));
	memset(pw,0,sizeof(pw));
}
int main(){
	freopen("oulipo.in","r",stdin);
	freopen("oulipo.out","w",stdout);
    scanf("%d",&T);
	while(T--){
		first_();
		cin>>s1>>s2;
		int l1 = s1.length(),l2 = s2.length();
		for(int i = 0;i < l1;i++)h = h * P + s1[i];
		pw[0] = 1,ha[0] = 0;
		for(int i = 0;i < l2;i++){
			ha[i+1] = ha[i] * P + s2[i];
			pw[i+1] = pw[i] * P;
		}
		for(int i = l1;i <= l2;i++){
			if(h == ha[i] - ha[i-l1] * pw[l1])ans++;
		}
		printf("%d\n",ans);
	}
	
	return 0;
	
}