记录编号	230858	评测结果	EEE
题目名称	[POJ 3461] 乌力波	最终得分	0
用户昵称	FoolMike	是否通过	未通过
代码语言	C++	运行时间	0.225 s
提交时间	2016-02-24 13:49:48	内存使用	0.70 MiB

#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
using namespace std;

const int maxl=100010;
string s,t;
int n,c,i,j,ls,lt,next[maxl]/*,ans[maxl]*/;

int main()
{
	freopen("oulipo.in","r",stdin);
	freopen("oulipo.out","w",stdout);
	scanf("%d",&n);
	for (;n>0;n--){
	scanf("%s%s",&t,&s);
	ls=s.size();lt=t.size();
	next[0]=-1;
	for (i=1;i<lt;i++){
		for (j=next[i-1];j!=-1&&t[j+1]!=t[i];j=next[j]);
		if (t[j+1]!=t[i]) next[i]=-1;else next[i]=j+1;
	}
	c=0;j=-1;
	for (i=0;i<ls;i++){
		while (j!=-1&&s[i]!=t[j+1]) j=next[j];
		if (t[j+1]==s[i]){
			j++;if (j==lt-1) c++;
		}
	}
	/*if (c==0) printf("There must be something wrong.\n");
	else{*/
		printf("%d\n",c);
		/*for (i=1;i<=c;i++) printf("%d\n",ans[i]);
	}*/
	}
	return 0;
}