记录编号	173985	评测结果	A
题目名称	[POJ 3461] 乌力波	最终得分	100
用户昵称	一個人的雨	是否通过	通过
代码语言	C++	运行时间	0.288 s
提交时间	2015-07-30 21:30:16	内存使用	0.43 MiB

#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=30010;
int next[maxn];
string s1,s2;
int ans=0;

void getfail(){
	next[0]=0; next[1]=0;
	for (int i=1;i<s1.size();++i){
		int j=next[i];
		while (j!=0&&s1[i]!=s1[j]) j=next[j];
		if (s1[i]==s1[j]) next[i+1]=j+1;
		   else next[i+1]=0;
	}
}

void kmp(){
	int j=0;
	for (int i=0;i<s2.size();++i){
		while (j&&s2[i]!=s1[j]) j=next[j];
		if (s2[i]==s1[j]) j++;
		if (j==s1.size()) ans++;
	}
}

int main()
{
	freopen("oulipo.in","r",stdin);
	freopen("oulipo.out","w",stdout);
	int t;
	scanf("%d",&t);
	while (t--){
		cin>>s1>>s2;
		getfail();
		ans=0;
		kmp();
		printf("%d\n",ans);
	}
}