记录编号	393747	评测结果	A
题目名称	[POJ 3461] 乌力波	最终得分	100
用户昵称	YGOI_真神名曰驴蛋蛋	是否通过	通过
代码语言	C++	运行时间	0.034 s
提交时间	2017-04-12 06:25:43	内存使用	6.01 MiB

#include <cstdio>
const int MAXN=1000010;
char stra[MAXN],strb[MAXN];
int next[MAXN];
void getNext(char pat[],int next[]) {
	next[0]=next[1]=0;
	for(int i=1;pat[i];++i) {
		int j=next[i];
		while(j&&pat[i]!=pat[j])j=next[j];
		next[i+1]=pat[i]==pat[j]?j+1:0;
	}
}
int match(char txt[],char pat[]) {
	getNext(pat,next);
	int j=0,cnt=0;
	for(int i=0;txt[i];++i) {
		while(j&&txt[i]!=pat[j])j=next[j];
		if(txt[i]==pat[j])++j;
		if(!pat[j])++cnt;
	}return cnt;
}
int main(){
	freopen("oulipo.in","r",stdin);
	freopen("oulipo.out","w",stdout);
	int T;scanf("%d",&T);
	while(T-->0) {
		scanf("%s",stra);
		scanf("%s",strb);
		printf("%d\n",match(strb,stra));
	}
	return 0;
}