LA 3026 && POJ 1961 Period （KMP算法）

题意：给定一个长度为n字符串s，求它每个前缀的最短循环节。也就是对于每个i（2<=i<=n)，求一个最大整数k>1（如果存在），使得s的前i个字符组成的前缀是某个字符串重复得k次得到的。输出所有的的k和i。

析：首先这是一个KMP的一个题（据大神们说这是一个水题。。。），首先要对KMP有了解，如果没有了解的先看一下，提供一个地址学习KMP算法，

http://www.cnblogs.com/dwtfukgv/articles/5532277.html

对KMP有所了解后，其实这就是一个对失配函数（f[x]）的运用，首先来说，我们对根据它的定义，“错位部分”长度为i-f[i]。如果这i个字符组成一个周期串的话，那么“错位”部分恰好必须是一个循环节，因此k*（i-f[i]） = i，（注意中k>1，所以i-f[i]!=i,也就是必须有f[i] > 0）。反过来也成立。如果对KMP了解了，那么应该是挺简单的理解的。

代码如下：

#include <iostream>

#include <cstdio>

using namespace std;

const int maxn = 1000000 + 10;

char p[maxn];

int f[maxn];

int main(){

    int n, kase = 0;

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

        scanf("%s", p);

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

        for(int i = 1; i < n; ++i){

            int j = f[i];

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

            f[i+1] = (p[i] == p[j] ? j+1 : 0);

        }

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

        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]));

        printf("\n");

    }

    return 0;

}

巴特西

LA 3026 && POJ 1961 Period （KMP算法）

最新文章

热门文章