SDUTOJ 2476Period

SDUTOJ 2476Period

#include
#include
#include
#define N 1000010
using namespace std;
char s[N];
int next[N];
void getnext(char s[])
{
	int j=-1,i=0,len;
	next[0]=-1;
        len=strlen(s);
	while(i<=len)
	{
		if(j==-1||s[i]==s[j])
		{
			++i;
			++j;
			next[i]=j;
		}
		else
		    j=next[j];
	}
}
int main()
{
	int j=1,i,n;
	while(cin>>n)
	{
		if(n==0)
		{
			break;
		}
		else
		cin>>s;
		getnext(s);
		cout<<"Test case #"<