View Code of Problem 3066

# include <stdio.h>
# include <string.h>
int n = 0;
char str1[10005],str2[1000005];
int next[10005];
int len1,len2;
void kmp(){
	len1=strlen(str2);
	len2=strlen(str1);
	int i;
	int j;
	i=0,j=-1;
	next[0]=-1;
	while(i<len2)
	{
		if(j==-1||str1[i]==str2[j])
		{
			 i++;
			 j++;
			 next[i]=j;
		}
		 else
			j=next[j];
	}
	i=0,j=0;
	while(i<len1&&j<len2)
	{
		if(j==-1||str2[i]==str1[j])
		{
			i++;
			j++;
			if(j==len2)
			{
				n++;
				j=next[j];
			}
		}
		else
			j=next[j];
	}
}

int main(){
	int num = 0;
	scanf("%d",&num);
	while(num--){
		n = 0;
		scanf("%s%s",&str1,&str2);
		kmp();
		printf("%d\n",n);
	}
	return 1;
}