记录编号	126194	评测结果	A
题目名称	[POJ 3461] 乌力波	最终得分	100
用户昵称	水中音	是否通过	通过
代码语言	C++	运行时间	0.299 s
提交时间	2014-10-11 18:50:33	内存使用	4.13 MiB

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
string s1,s2;
int n,m,h,i,l,p,k=0,next[1000010]={0};
void get_next()
{
	memset(next,0,sizeof(next));
	m=s1.size();p=0;
	for(l=1;l<m;l++)
	{
		while(p&&s1[p]!=s1[l])p=next[p];
		if(s1[p]==s1[l])next[l+1]=++p;
		else next[l+1]=0;
	}
	h=s2.size();p=0;
	for(l=0;l<h;l++)
	{
		while(p&&s1[p]!=s2[l])p=next[p];
		if(s1[p]==s2[l]){p++;if(p==m)k++;}
	}
}
int main()
{
	freopen("oulipo.in","r",stdin);
	freopen("oulipo.out","w",stdout);
	scanf("%d",&n);
	for(i=1;i<=n;i++)
	{
		k=0;
		cin>>s1;
		cin>>s2;
		get_next();
		printf("%d\n",k);
	}
	return 0;
}