KMP算法之查找模式串在源串中出现的次数

问题描述：

给定两个字符串T, P。查找字符串P在字符串T中出现的次数。

解决方法：

典型的KMP算法的题目，在此使用的KMP算法为算法导论上介绍的算法。下一篇文章将详细介绍KMP算法的计算过程。

题目链接：

http://hihocoder.com/problemset/problem/1015

源代码如下：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define M 9999
#define N 999999
char t[N], p[M];
int *getprefix(char p[])
{
	int *h, plen, k, i;
	plen = strlen(p);
	h = (int *)malloc(plen*sizeof(int));
	h[0] = 0;
	k=0;
	for(i=1; i<plen; i++)
	{
		while(k>0 && p[k]!=p[i])
			k=h[k-1];
		if(p[k] == p[i])
			k++;
		h[i]=k;
		
	}
	return h;
}
int kmp_matcher(char t[], char p[])
{
	int count;
	int *h, tlen, plen, i, q;
	tlen = strlen(t);
	plen = strlen(p);
	h = getprefix(p);
	count = 0;
	q=0;
	for(i=0; i<tlen; i++)
	{
		while(q>0 && t[i]!=p[q])
			q = h[q-1];
		if(t[i] == p[q])
			q++;
		if(plen == q)
		{
			count++;
		
			q = h[q-1];
		}
	}
	return count;
}
int main()
{
	
	int n, ans;
	scanf("%d
",&n);
	while(n--)
	{
		gets(p);	gets(t);
		ans = kmp_matcher(t, p);
		printf("%d
", ans);
	}
	return 0;
}