第三周下 kmp

E - Period HDU - 1358
题意
求一串字符中的前缀中有多少最大周期数，例如“aaa”中，前两个“aa”最小周期长度为“a”，因此周期长度为2，前三个“aaa”的最小周期也是“a”因此周期长度为3；再如“aabaabaabaab”中前6个“aabaab”的最小周期长度为“aab”，因此周期为2.前9个有3个aab，因此周期长度为三
输出第一个数是你所截取的字符串长度，第二个数是有几个循环周期
aabaab”的前缀next[]数组的存储是这样的{0, 1, 0, 1, 2, 3}web

#include<stdio.h>
#include<string.h>
using namespace std;
const int N=1000002;
char s1[N],s2[N];
int next[N];
void gnext(int l)
{
	int i=0,j=-1;
	next[0]=-1;
	while(i<l)
	{
		if(j==-1||s1[i]==s1[j])
		{
			++i,++j;
			next[i]=j;
		}
		else j=next[j];
	}
}
int main()
{
	int n,q=1;
	while(~scanf("%d",&n)&&n)
	{
		scanf("%s",s1);
		int l1=strlen(s1);
		gnext(l1);
		printf("Test case #%d\n",q++);
		for(int i=1;i<=n;i++)
        {
            if(!next[i])
                continue;
            int k=i-next[i];
            if(i%k==0)
                printf("%d %d\n",i,i/k);
        }
		printf("\n");
	}
	return 0;
}