记录编号	174002	评测结果	A
题目名称	[POJ 3461] 乌力波	最终得分	100
用户昵称	forever	是否通过	通过
代码语言	C++	运行时间	0.048 s
提交时间	2015-07-31 06:26:33	内存使用	9.90 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int next[10010];
int n,num,len1,len2;
char a[10010],b[10000010];
void kmp(){
	int j=0;
	int i=0;
	while(i!=len2&&j!=len1){
		if(j==-1||a[j]==b[i]){
			++i;
			++j;
		}
		else
		  j=next[j];
		if(j==len1){
			num++;
			j=next[j];
		}
	}
	printf("%d\n",num);
}
void getnext(){
	int j=-1;
	next[0]=-1;
	int i=0;
	while(i<len1){
		if(j==-1||a[i]==a[j])
		  next[++i]=++j;
		else
		  j=next[j];
	}
	kmp();
}
int main(){
	freopen("oulipo.in","r",stdin);
	freopen("oulipo.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		scanf("%s%s",a,b);
		num=0;
		//memset(next,0,sizeof(next));
		len1=strlen(a);
		len2=strlen(b);
		getnext();
	}
}