hdu1358——Period

题意：类似周期

思路：利用kmp中的next[]直接解决。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
char s[1000002];
int next[1000002];
int n;
void getnext(char s[],int next[],int len)
{
	next[0]=-1;
	int j=-1;
	for(int i=1;i<len;i++)
	{
		while(j>-1&&s[j+1]!=s[i])
			j=next[j];
		if(s[j+1]==s[i])  j++;
		next[i]=j;
	}
}
int main()
{
	int ca=1;
	while(1)
	{
		cin>>n;
		if(n==0) break;
		scanf("%s",s);
		getnext(s,next,n);
		printf("Test case #%d\n",ca++);
		for(int i=2;i<=n;i++) 
		{
			if(i%(i-next[i-1]-1)==0&&next[i-1]!=-1)
			{
				printf("%d %d\n",i,i/(i-next[i-1]-1));
			}
		}
		cout<<endl;
	}
	return 0;
}