POJ-1961 Period

タイトルリンク:http://poj.org/problem?id=1961
テーマ:
文字列をあげて、この文字列からi番目の文字までのループの回数を求めます.
例えばaabaabaabは、長さが12から2番目のaの場合、aが2回、出力2.から2番目のbの場合、aabが2回、出力2.から3番目のbの場合、aabが3回、出力3.から4番目のbの場合、aabが4回、出力4.
問題解決の考え方:
この問題はPOJ 2406の強化版のようです.その問題は1つの文字列を出力するループ節が現れる回数で、これはi番目の文字までで、実は1つのループが増えたのです.この文字列を一度遍歴すればいいです.その問題が終わったついでに、この問題をAさんにあげました.
コードは次のとおりです.

#include<iostream>
#include<cstring>
#include<cstdio>
#include<string>
#include<algorithm>
using namespace std;
#define N 1000010

char s[N];
int nextval[N];
int len;

void getnext(const char *s)
{
	int i = 0, j = -1;
	nextval[0] = -1;
	while(i != len)
	{
		if(j == -1 || s[i] == s[j])
			nextval[++i] = ++j;
		else
			j = nextval[j];
	}
}

int main()
{
	int T = 1;
	int length, add;
	while(scanf("%d", &len) && len)
	{
		scanf("%s", s);
		getnext(s);
		printf("Test case #%d
", T++);
		for(int i = 1; i <= len; ++i)
		{
			length = i - nextval[i]; //      
			if(i != length && i % length == 0) //       
				printf("%d %d
", i, i / length);
		}
		printf("
");
	}
	return 0;
}