记录编号	94085	评测结果	AAA
题目名称	[POJ 3461] 乌力波	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.168 s
提交时间	2014-03-30 11:16:39	内存使用	6.04 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iomanip>
using namespace std;
const int SIZEL=1000010;
char word[SIZEL],text[SIZEL];
int next[SIZEL]={0};
void getnext(char *s,int n,int *next){//字符串s,文本下标0~n-1,结果存于f
	next[0]=-1;//这是一个特例
	int i=0,j=-1;
	while(i<n){
		while(j!=-1&&s[i]!=s[j]) j=next[j];
		next[++i]=++j;//如果在这个位置失配了应该去哪试图配
	}
}
int KMP(char *S,int n,char *T,int m){//目标串S的前n个中出现了几次模式串T的前m个
	int i=0,j=0;
	int ans=0;
	getnext(T,m,next);
	while(i<n){
		while(j!=-1&&S[i]!=T[j]) j=next[j];
		i++,j++;
		if(j==m) ans++;
	}
	return ans;
}
int main(){
	freopen("oulipo.in","r",stdin);
	freopen("oulipo.out","w",stdout);
	int T;
	scanf("%d",&T);
	while(T--){
		scanf("%s%s",word,text);
		printf("%d\n",KMP(text,strlen(text),word,strlen(word)));
	}
	return 0;
}