#include<iostream>
#include<cstring>
using namespace std;
int next1[1000010];
char aa[1000010];
char bb[1000010];
int n,m;
void getnext(char a[])
{
	int i=0,j=-1;
	next1[0]=-1;
	while(i<n)
	{
		if(j==-1 || a[j]==a[i])
		{
			++j;
			++i;
			if(a[i]!=a[j]) next1[i]=j;
			else next1[i]=next1[j];
		}
		else
		{
			j=next1[j];
		}
	}
}
int KMPindex(char b[],char a[],int pos)
{
	int i=pos;
	int j=0;
	while(i<m && j<n)
	{
		if(j==-1 || b[i]==a[j])
		{
			++i;
			++j;
		}
		else j=next1[j];
	}
	if(j>=n)	return i-n+1;
	else return -1;
}
int main()
{
	int x;
	cin>>x;
	while(x--)
	{
		int count=0;
	        cin>>aa;
	        getchar();
 	        cin>>bb;
		n=strlen(aa);
		m=strlen(bb);
		getnext(aa);
		for(int i=0;i<m;i++)
		{
			i=KMPindex(bb,aa,i);
			if(i!=-1) 
			{
				count++;
			}
			else break;
		}
		cout<<count<<endl;
	}
	return 0;
}

• Re:为什么会超时啊。。。。 (1047) 15153175787 2014-10-23 16:21:38
• Re:为什么会超时啊。。。。 (43) tangguojun 2017-09-14 15:53:16