前言

重新写了KMP的模板，这回完全照搬《算法导论》P926的伪代码。

题目大意

给出两个字符串，问第二个字符串中存在多少个字串能与第一个字符串匹配。

思路

KMP模板题。

代码

#include<iostream>
#include<stdio.h>
using namespace std;
#define T_SIZE 1000000
#define P_SIZE 10000
int next[P_SIZE+2];
char T[T_SIZE+2],P[P_SIZE+2];
//T是被匹配的串。
//P是模式串。
void COMPUTE_PREFIX_FUNCTION(char P[])
{
	int m=strlen(P+1);
	next[1]=0;
	for(int k=0,q=2;q<=m;q++)
	{
		while(k>0&&P[k+1]!=P[q])
			k=next[k];
		if(P[k+1]==P[q])
			k++;
		next[q]=k;
	}
}
int KMP_MATCHER(char T[],char P[])
{
	int n=strlen(T+1),m=strlen(P+1);
	COMPUTE_PREFIX_FUNCTION(P);
	int sum=0;
	for(int i=1,q=0;i<=n;i++)
	{
		while(q>0&&P[q+1]!=T[i])
			q=next[q];
		if(P[q+1]==T[i])
			q++;
		if(q==m)
		{
			sum++;
			q=next[q];
		}
	}
	return sum;
}
int main()
{
	int t;
	for(scanf("%d",&t);t>0;t--)
	{
		scanf("%s%s",P+1,T+1);
		//字符串都是从下标1开始的。 
		printf("%d\n",KMP_MATCHER(T,P));
	}
}