记录编号	282302	评测结果	A
题目名称	[POJ 3461] 乌力波	最终得分	100
用户昵称	SOBER GOOD BOY	是否通过	通过
代码语言	C++	运行时间	0.050 s
提交时间	2016-07-13 14:42:10	内存使用	6.15 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int N,f[1020010],M;
char s1[1020050],s2[1020050];
int Ans=0;
int T;
void build(void);
//看s2能否和s1匹配上 
int main()
{	
	freopen("oulipo.in","r",stdin);freopen("oulipo.out","w",stdout);
	scanf("%d",&T);
	while(T--)
	{
	scanf(" %s %s",s2,s1);
	N=strlen(s1);M=strlen(s2);
	build();
	int j=0;
	for(int i=0;i<N;i++)
	{
		while(j&&s1[i]!=s2[j])j=f[j];
		//printf("%d %d\n",i,j);
		if(s1[i]==s2[j])j++;
		if(j==M)Ans++;
	}
	printf("%d\n",Ans);
	memset(f,0,sizeof(f));
	//memset(s1,0,sizeof(s1));
	//memset(s2,0,sizeof(s2));
	Ans=0;
	}
	
}
void build(void)
{	f[0]=f[1]=0;
	for(int i=1;i<M;i++)
	{
		int j=f[i];
		while(j&&s2[i]!=s2[j])j=f[j];
		f[i+1]=s2[i]==s2[j]?j+1:0;
	}
}