poj 1961 Period(KMP)

http://poj.org/problem?id=1961

题意：

这道题的题意真是晦涩。。。

给你一个字符串，求这个字符串到第i个字符为止的循环节的次数。

比如aabaabaabaab，长度为12.到第二个a时，a出现2次，输出2.到第二个b时，aab出现了2次，输出2.到第三个b时，aab出现3次，输出3.到第四个b时，aab出现4次，输出4.

#include <string.h>
#include <stdio.h>
int n;
char str[1000005];
int next[1000001];

void get_next()
{
	int i;
	int j;
	i = 0;
	j = -1;
	next[0] = -1;
	while(str[i])
	{
		if(j == -1 || str[i] == str[j])
		{
			i++;
			j++;
			next[i] = j;
		}
		else
			j = next[j];
	}
}

int main()
{
	int item = 1;
	while(~scanf("%d",&n)&&n)
	{
		scanf("%s",str);
		get_next();

		printf("Test case #%d\n",item++);

		for(int i = 2; i <= n; i++)
		{
			int t = i - next[i];
			if(i%t == 0 && i/t > 1)
				printf("%d %d\n",i,i/t);
		}
		printf("\n");
	}
	return 0;
}

poj 1961 Period(KMP)

原文：http://blog.csdn.net/u013081425/article/details/19173735