POJ3461-KMP算法的简单运用

 

求一个主串中有多少个给定的子串

直接KMP模板就OK了

#include<iostream>
using namespace std;
#define  len  1000100
char s[len];
char t[len];
int next[len];

void getnext()
{
	int i=0;
	int j=-1;
	next[0]=-1;
	int lent=strlen(t);
	while(i<lent)
	{
		if (j==-1||t[i]==t[j])
		{
			i++;
			j++;
			next[i]=j;
		}
		else
		{

			j=next[j];
		}
	}
}


int KMP()
{
	int i=0;
	int j=0;
	int  k=0;
	int slen=strlen(s);
	int tlen=strlen(t);
	getnext();
	while (i<slen)
	{
		if (j==-1||s[i]==t[j])
		{
			i++;
			j++;
			if (j==tlen)
			{
				k++;
			}
			//next[i]=j;
		}
		else
		{

			j=next[j];
		}
	}
	return k;
}
int main()
{
	int num;
	scanf("%d",&num);
	while (num--)
	{
		scanf("%s",t);
		scanf("%s",s);
		cout<<KMP()<<endl;
	}
	
	//cout<<endl;
}