poj 题目链接：http://poj.org/problem?id=1961
hdu题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1358
Description
Input
Output
Sample Input
3 aaa 12 aabaabaabaab 0
Sample Output
Test case #1 2 2 3 3 Test case #2 2 2 6 2 9 3 12 4
Source
题意：
给出一个字符串，求这个字符串到第i个字符为止的循环节的次数。
比如aabaabaabaab，长度为12.到第二个a时，a出现2次，输出2.到第二个b时，aab出现了2次，输出2.到第三个b时，aab出现3次，输出3.到第四个b时，aab出现4次，输出4.
代码如下：
#include<cstdio>
#include<cstring>
#include<string>
#define N 1000017
int next[N];
int len;
void getnext(char s[])
{
int i = 0, j = -1;
next[0] = -1;
while(i < len)
{
if(j == -1 || s[i] == s[j])
{
i++;
j++;
next[i] = j;
}
else
j = next[j];
}
}
int main()
{
char s[N];
int cas = 0;
int length;
while(scanf("%d", &len) && len)
{
scanf("%s", s);
getnext(s);
printf("Test case #%d\n", ++cas);
for(int i = 1; i <= len; i++)
{
length = i - next[i];//循环节的长度
if(i != length && i % length == 0)//如果有多个循环
printf("%d %d\n", i, i / length);
}
printf("\n");
}
return 0;
}
poj1961 & hdu 1358 Period（KMP）,布布扣,bubuko.com
poj1961 & hdu 1358 Period（KMP）
原文：http://blog.csdn.net/u012860063/article/details/38532145