首页 > POJ解题报告 > POJ 3461 Oulipo[KMP]

POJ 3461 Oulipo[KMP]

求子串在主串中出现的次数,KMP匹配即可。
传送:POJ 3461 Oulipo http://poj.org/problem?id=3461

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
using namespace std;
 
#define MAIN_MAX_COUNT 1000010
#define SUB_MAX_COUNT 10010
 
char mStr[MAIN_MAX_COUNT], pStr[SUB_MAX_COUNT];
 
void GetNextArray(char pstr[], int nextarr[])
{
	int m = strlen(pstr);
	int k, q;
	nextarr[0] = -1;
	k = -1;
 
	for (q = 1; q < m; ++q)
	{
		while (k >= 0 && pstr[k + 1] != pstr[q])
			k = nextarr[k];
		if (pstr[k + 1] == pstr[q])
			++k;
		nextarr[q] = k;
	}
} 
 
int KmpMatcher(char mstr[], char pstr[])
{
	int n = strlen(mstr);
	int m = strlen(pstr);
	int *nextarr = (int *)malloc(m * sizeof(int));
	int i, q = -1, tms = 0;
 
	GetNextArray(pstr, nextarr);
 
	for (i = 0; i < n; ++i)
	{
		while (q >= 0 && pstr[q + 1] != mstr[i])
			q = nextarr[q];	
		if (pstr[q + 1] == mstr[i])
			++q;
		if (q == m - 1)
		{
			++tms;
			q = nextarr[q];
		}
	}
	free(nextarr);
	return tms;
}
 
int main(int argc, char **argv)
{
	//freopen("in.txt", "r", stdin);
	//freopen("out.txt", "w", stdout);
 
	int n;
	scanf ("%d%*c", &n);
	while (n--)
	{
		memset(mStr, 0, sizeof(mStr));
		memset(pStr, 0, sizeof(pStr));
		gets(pStr);
		gets(mStr);
		printf ("%d\n", KmpMatcher(mStr, pStr));
	}
 
	return 0;
}

觉得文章还不错?点击此处对作者进行打赏!


本文地址: 程序人生 >> POJ 3461 Oulipo[KMP]
作者:代码疯子(Wins0n) 本站内容如无声明均属原创,转载请保留作者信息与原文链接,谢谢!


更多



分类: POJ解题报告 标签: ,
  1. 2011年9月8日09:58 | #1

    看来老兄你比较喜欢研究算法,呵

    [回复]

    代码疯子 回复:

    @代码部落(Winson), 呵呵 没事看一点 算是复习 也不是很喜欢专门来研究这个东西。

    [回复]