poj 1961 Period(kmp最短循环节)

题目链接 

Description

题意：

     给定一个长度为n的字符串s，求他每个前缀的最短循环节。换句话说，对于每个i（2<=i<=n），求一个最大的整数k（如果k存在），使得s的前i个字符可以组成的前缀是某个字符串重复k次得到的。输出所有存在K的i和对应的k。

    这是刘汝佳《算法竞赛入门经典训练指南》上的原题（p213），用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\n",t++);
        for (int i = 2; i <= n; i++)
        {
            if (f[i] > 0 && i % (i-f[i]) == 0)
                printf("%d %d\n",i, i / (i-f[i]));
        }
        puts("");
    }
    return 0;
}

文章来源: xindoo.blog.csdn.net，作者：xindoo，版权归原作者所有，如需转载，请联系作者。

原文链接：xindoo.blog.csdn.net/article/details/8764044