Period

Period
题意
若字符串 s s s的前缀s[1~i]，2 <=i <= n，是由长度为len的最小循环元循环k次而成，则输出这个前缀字符串的长度以及循环次数k。
思路
字符串 s s s的前缀s[1~i]，2 <=i <= n，具有长度为len的最小循环元，则len能整除i，并且s[len+1 ~ i] = s[1 ~ i - len]，既next[i] = i - len，所以最小循环元的长度len = i - next[i]，循环次数为i / len。
code

#include<iostream>
#include<cstdio>
using namespace std;
const int N = 1e6+5;
int t, n, net[N];
char a[N];
void calc_next()
{
    net[1] = 0;
    for(int i = 2, j = 0; i <= n; i++)
    {
        while(j && a[i] != a[j+1])
            j = net[j];
        if(a[i] == a[j+1])
            j++;
        net[i] = j;
    }
}
int main()
{
    while(cin >> n && n)
    {
        cin >> (a+1);
        calc_next();
        printf("Test case #%d\n", ++t);
        for(int i = 2; i <= n; i++)
        {
            if(i % (i-net[i]) == 0 && i / (i-net[i]) > 1)
                printf("%d %d\n", i, i / (i-net[i]));
        }
        puts("");
    }
    return 0;
}