【HDU 1358】Period（KMP求字符串周期）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1358

题意：

对于一个字符串的所有前缀中，如果某个前缀的周期大于1就输出此前缀的长度和它循环节的个数。

思路：

求出每个字符串的next数组，还要知道 i - nxt [ i ]是每个前缀的循环节长度，然后判断前缀的长度是否是循环节的倍数就可以了。

My  Code：

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<queue>
#include<math.h>
#include<set>
using namespace std;
#define INF 1e9
typedef long long ll;
char ch[1000005];
int nxt[1000005],len1;
void GetNext()///求next数组 
{
    int j = 0,k = -1;
    nxt[0] = -1;
    while(j < len1)
    {
        if(k == -1 || ch[j] == ch[k])
        {
            j++;k++;
            nxt[j] = k;
        }
        else k = nxt[k];
    }
}
int main()
{
	int t = 0;
    while(~scanf("%d",&len1) && len1)
    {
    	getchar();
    	memset(ch,'\0',sizeof(ch));
    	scanf("%s",ch);
    	printf("Test case #%d\n",++t);
    	GetNext();
    	for(int i = 2; i <= len1; i++)
    	{
    		int ans = i-nxt[i];///计算出循环节的长度 
    		if(i/ans > 1 && i%ans == 0)///周期要大于1并且前缀的长度必须是循环节长度的倍数 
    			printf("%d %d\n",i,i/ans);
		}
		printf("\n");
	}

    return 0;
}