#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
using namespace std;

int n,la,lb;
int next[100010];
char a[1000010],b[100010];

void getnext()
{
	int j=-1;
	next[0]=-1;
	for(int i=1;i<lb;i++)
	{
		if(j!=-1 && b[j+1]!=b[i])	j=next[j];
		if(b[j+1]==b[i])	j++;
		next[i]=j;
	}
}

int kmp()
{
	int ans=0;
	int j=-1;
	for(int i=0;i<la;i++)
	{
		if(j!=-1 && a[i]!=b[j+1])	j=next[j];
		if(b[j+1]==a[i])	j++;
		if(j==lb-1)	
		{
			ans++;	
			j=next[j];
		}	
	}
	return ans;
}

int main()
{
	scanf("%d",&n);
	for(int u=1;u<=n;u++)
	{
		scanf("%s %s",b,a);
		la=strlen(a);
		lb=strlen(b);
		getnext();
		printf("%d\n",kmp());
	}
}

• Re:C++福利 (799) smlq123 2016-07-21 13:28:28
• Re:C++福利 (799) smlq123 2016-07-21 13:28:42