记录编号	573163	评测结果	AAA
题目名称	[POJ 3461] 乌力波	最终得分	100
用户昵称	Hzoi_Mafia	是否通过	通过
代码语言	C++	运行时间	0.471 s
提交时间	2022-07-20 10:24:07	内存使用	16.24 MiB

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int T,n,m,pi[2000005];
char s[10005],t[1000005],pj[2000005];
int main(){
	freopen("oulipo.in","r",stdin);
	freopen("oulipo.out","w",stdout);
	scanf("%d",&T);
	while(T--){
		scanf("%s%s",s+1,t+1);n=strlen(s+1),m=strlen(t+1);int ans(0);
		for(int i=0;i<n;++i)
			pj[i]=s[i+1];
		pj[n]='#';
		for(int i=1;i<=m;++i)
			pj[i+n]=t[i];
		pi[0]=0;
		for(int i=1,j;i<=m+n;++i){
			j=pi[i-1];
			while(j&&pj[i]!=pj[j])j=pi[j-1];
			if(pj[i]==pj[j])++j;
			pi[i]=j;
		}
		// for(int i=0;i<=n+m;++i)
			// cout<<i<<' '<<pj[i]<<' '<<pi[i]<<endl;
		for(int i=n+1;i<=n+m;++i)
			if(pi[i]==n)
				++ans;
		printf("%d\n",ans);
	}
}