#include<iostream>
#include<cstring>
using namespace std;
#define N 1001000

struct String
{
	char s[N];
	int len;
};
String S, T;
int next[N];
int getnext()
{
	int i,j;
    next[1]=0;
    j=0;
    for(i=2;i<=T.len;i++)
    {
        while(j>0&&T.s[j+1]!=T.s[j])j=next[j];
        if(T.s[j+1]==T.s[i])j=j+1;
        next[i]=j;
    }
	return 0;
}
int kmp()
{
 	int i,j;
	j=0;
	int cn=0;
	for(i=1;i<=S.len;i++)
	{
		while(j>0&&T.s[j+1]!=S.s[i])j=next[j];
 		if(T.s[j+1]==S.s[i])j=j+1;
		if(j==T.len)
		{
			//printf("%dggg  \n",i-T.len);
			cn++;
			j=next[j];
		}	
	}
	return cn;
}
char ss[N],tt[N];
int main()
{
	int i;
	int ca;
	int len1;
	//while(cin>>ca)
	//freopen("kmp.in","r",stdin);
	//freopen("kmp.out","w",stdout);
//	while(scanf("%d",&ca)!=EOF)
	scanf("%d",&ca);
	{
		while(ca--)
		{
			//cin>>tt>>ss;
			scanf("%s%s",tt,ss);
			len1=strlen(ss);
			S.len=len1;
			for(i=0;i<len1;i++)
			{
				S.s[i+1]=ss[i];
			}
			len1=strlen(tt);
			T.len=len1;
			for(i=0;i<len1;i++)
			{
				T.s[i+1]=tt[i];
			}
			//get_nextval();
			getnext();
			int res=kmp();
			//int res=Index_KMP(1);
			/*int cn=0;
			while(res!=0)
			{
                cn++;
                res=Index_KMP(res+1);
            }*/
			//cout<<cn<<endl;
			printf("%d\n",res);
		}
	}
	
	return 0;
}

• Re:kmp为什么不过？ (1098) sailors 2007-11-08 17:50:07
• char[max_n]貌似比较慢? (12) zhaokkk27 2008-05-01 12:59:08