POJ1961:Period 题解

主要思路

这道题要求在一个循环前缀中求出最小周期长度和最大频率。我们可以用 KMP 的 next 数组来解这个问题。我们先来回顾一下 next 数组的含义。\(next[i]\)代表在区间\(str[1,i]\)中前缀后缀的最长公共部分。如果区间长度是\(next[i]\)的倍数，那么其中就有循环节。详细见代码。

代码

// POJ1961.cpp
#include <iostream>
#include <cstdio>

using namespace std;
const int maxn = 1000000 + 1000;
int next[maxn];
string str;

int main()
{
    int siz = 0, cnt = 1;
    while (scanf("%d", &siz) && siz != 0)
    {
        cin >> str;
        // get the next array;
        next[0] = -1;
        for (int i = 1; i < siz; i++)
        {
            int j = next[i - 1];
            while (j >= 0 && str[i] != str[j + 1])
                j = next[j];
            if (str[i] == str[j + 1])
                next[i] = j + 1;
            else
                next[i] = -1;
        }
        for (int i = 0; i < siz; i++)
            ++next[i];
        // we have got it...;
        printf("Test case #%d\n", cnt++);
        for (int i = 1; i < siz; i++)
            if ((i + 1) % (i - next[i] + 1) == 0 && (i + 1) / (i - next[i] + 1) > 1)
                printf("%d %d\n", i + 1, (i + 1) / (i - next[i] + 1));
        puts("");
    }
    return 0;
}