POJ 1961 KMP 求前缀循环节 位置及次数 -电脑资料

    #include

    #include

    #define N 1000100

    char T[N];

    int f[N], len;

    void getFail(){

    f[0] = f[1] = 0;

    for(int i = 1; i < len; i++)

    {

    int j = f[i];

    while(j && T[i]!=T[j]) j = f[j];

    f[i+1] = T[i] == T[j]? j+1: 0;

    }

    }

    int main(){

    int Cas = 1;

    while(scanf("%d",&len), len){

    scanf("%s",T);

    printf("Test case #%d\n",Cas++);

    getFail();

    for(int i = 1; i <= len; i++)

    {

    int length = i - f[i]; //循环节长度

    if(i != length && i%length == 0)

    printf("%d %d\n", i, i/length);

    }

    printf("\n");

    }

    return 0;

    }