记录编号	293642	评测结果	A
题目名称	[POJ 3461] 乌力波	最终得分	100
用户昵称	dateri	是否通过	通过
代码语言	C++	运行时间	0.119 s
提交时间	2016-08-11 00:09:30	内存使用	1.17 MiB

#include<cstdio>
#include<cstring>
using namespace std;
int main()
{
	freopen("oulipo.in","r",stdin);
	freopen("oulipo.out","w",stdout);
	int m,n,i,t,count,ans=0,p,j;
	char a[10005],b[1000005];
	int next[10005];
	scanf("%d",&t);
	while(t--)
	{
		ans=0;
		scanf("%s%s",a+1,b+1);
		n=strlen(a+1);
		m=strlen(b+1);
		next[1]=0;
		for(i=2;i<=n+1;i++)
		{
		  p=next[i-1];
		  while(a[i-1]!=a[p]&&p>0) p=next[p];
		  next[i]=p+1;
		}
		//for(i=1;i<=n+1;i++)
		  //printf("%d ",next[i]);
		for(i=1,j=1;i<=m;)
		{
			if(j==0||a[j]==b[i]) 
			{
			  j++;
			  i++;
			  if(j>n)
			  ans++,j=next[j];
			}
			else
			  while(a[j]!=b[i]&&j>0)
			    j=next[j];
		}
	    printf("%d\n",ans);
	}
	return 0;
}