记录编号	95201	评测结果	A
题目名称	[POJ 3461] 乌力波	最终得分	100
用户昵称	Chenyao2333	是否通过	通过
代码语言	C++	运行时间	0.040 s
提交时间	2014-04-04 18:37:17	内存使用	1.32 MiB

#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<iostream>

using namespace std;

const int MAXW=10000+100;
const int MAXT=1000000+100;

struct kmp{
	int w_len;
	int f[MAXW];
	
	int get_fail(char* word){
		memset(f,0,sizeof(f));
		f[0]=f[1]=0;
		w_len=strlen(word);
		for(int i=1;i<w_len;i++){
			int x=f[i];
			while(x && word[i]!=word[x]){
				x=f[x];
			}
			f[i+1]= word[i]==word[x] ? x+1:0;
		}
	}
	
	int find(char *word,char *T){
		int x=0,ans=0;
		for(int i=0;T[i];i++){
			while(x && word[x]!=T[i])x=f[x];
			if(word[x]==T[i])x++;
			if(x==w_len)ans++;
		}
		return ans;
	}
	
	void test(){
		for(int i=0;i<=w_len;i++){
			printf("f[%d]=%d\n",i,f[i]);
		}
	}
	
}solver;

void open(){
	freopen("oulipo.in","r",stdin);
	freopen("oulipo.out","w",stdout);
}

char ch1[MAXW],ch2[MAXT];

void work(){
	int t;cin>>t;
	while((t--)>0){
		scanf("%s %s",&ch1,&ch2);
		solver.get_fail(ch1);
		//solver.test();
		cout<<solver.find(ch1,ch2)<<endl;
	}
}

int main(){
	//char ch[]={"abab"};
	//solver.get_fail(ch);
	//cout<<solver.find(ch,"ababaababab");
	//solver.test();
	
	open();
	work();
	return 0;
}