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",&n);

	while(n--)

	{

		gets(p);	gets(t);

		ans = kmp_matcher(t, p);

		printf("%d\n", ans);

	}

	return 0;

}

巴特西

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

最新文章

热门文章