POJ 3461

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
inline int read(){
	int x=0,f=1,ch=getchar();
	while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}
	while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}
	return x*f;
}
char word[10005];
int len1;
int nxt[10005];
inline void pre(){
	nxt[0]=-1;
	int j=0,k=-1;
	while(j<len1){
		// puts("X");
		if(k==-1||word[k]==word[j]) nxt[++j]=++k;
		else k=nxt[k];
	}
}
char text[1000005];
int len2;
inline int kmp(){
	int i=0,j=0,res=0;
	while(i<len2){
		if(j==-1||text[i]==word[j]) ++i,++j;
		else j=nxt[j];
		if(j==len1) res++,j=nxt[j];
	}
	return res;
}
int main(){
	int T=read();
	while(T--){
		scanf("%s",word);len1=strlen(word);
		scanf("%s",text);len2=strlen(text);
		pre();
		printf("%d\n",kmp());
	}
	return 0;
}