poj 1961 Period(kmp最短循環節)

テーマリンク 
Description
For each prefix of a given streing S with N characters(each character has an ASCII code between 97 and 126、inclusive)、we want to know w ther the prefix isa perdic sting.Thais、foreach i(2=the ah h h h h h h h h h h h h h h h h h h h h h h h h h h h h h h h h h h h h h h h h h h h h h h h h h h h h h h h h h h h h h h h h h h h h h h h h h h h h h h h h h h h h h h h h h h h h h h h h h h h h h h h h tten as A
K,that is A concatentated K times,for some string A.Of course,we also want to know the period K.………
件名:
     長さnの文字列sを与えて、彼の各プレフィックスの最短循環節を求めます.言い換えれば、i(2<=i<=n)毎に、最大の整数k(kが存在する場合)が求められ、sの最初のi文字で構成できるプレフィックスは、ある文字列がk回繰り返して得られる.Kが存在する全てのiと対応するkを出力します.
    これは劉汝佳の『アルゴリズムコンテスト入門古典訓練ガイド』の原題(p 213)で、KMP構造の状態で表を移動します.
問題解決コード(完全に白書参照):

//poj 1961
#include <stdio.h>
const int maxn = 1000000 + 10;

char p[maxn];
int f[maxn];

int main()
{
    int n, t = 1;
    while (scanf("%d",&n) && n)
    {
        scanf("%s",p);
        f[0] = 0;
        f[1] = 0;
        for (int i = 1; i < n; i++)
        {
            int j = f[i];
            while (p[i] != p[j] && j)
                j = f[j];
            f[i+1] = (p[i] == p[j] ? j+1 : 0);
        }/*      KMP       ,       ，
                   */
        printf("Test case #%d
",t++);
        for (int i = 2; i <= n; i++)
        {
            if (f[i] > 0 && i % (i-f[i]) == 0)
                printf("%d %d
",i, i / (i-f[i]));
        }
        puts("");
    }
    return 0;
}