2880490_ac_140ms_1092k.c

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <string.h>

char p[10001], t[1000001];
int n, m, ans;
int pai[10001];

void pre()
{
	int k, q;

	pai[1] = 0;
	k = 0;
	for(q = 2; q <= m; q++)
	{
		while(k>0&&p[k+1]!=p[q])
			k = pai[k];
		if(p[k+1]==p[q])
			k++;
		pai[q] = k;
	}
}

void kmp()
{
	int i, q;

	n = strlen(&t[1]);
	m = strlen(&p[1]);
	pre();
	q = 0;
	for(i = 1; i <= n; i++)
	{
		while(q>0&&p[q+1]!=t[i])
			q = pai[q];
		if(p[q+1]==t[i])
			q++;
		if(q==m)
		{
			ans++;
			q = pai[q];
		}
	}
}

int main()
{
	int cas;

	scanf("%d",&cas);
	while(cas--)
	{
		ans = 0;
		scanf("%s%s",&p[1],&t[1]);
		kmp();
		printf("%d\n",ans);
	}
	return 1;
}