一、题意

有kase组数据(kase<=200)。
每组数据一个字符串（长度<=1000），要求列出该字符串中，包含i个循环节的循环子串的最大长度。
输出列出的答案数组max_cir_len[i].

二、解析

循环节问题考虑使用KMP。
用KMP的Next数组只能求出前缀子串的循环节，而此题要求的是所有子串，因此需要枚举起始点。
考虑时间复杂度O(n^2)，不会超时。

三、代码

#include <iostream>
#include <string>
#include <cmath>
using namespace std;
const int maxn = 1000 + 5;
int kase, ans[maxn], Next[maxn];

void getNext(char* p, int m) {
    Next[0] = -1;
    int i = 0, j = -1;
    while(i < m) {
        if(j == -1 || p[i] == p[j]) i ++, j ++, Next[i] = j;
        else j = Next[j];
    }
}

int main() {
    cin >> kase;
    for(int k = 1; k <= kase; k ++) {
        string str;
        cin >> str;
        int n = str.size();
        fill(ans, ans + n + 1, 0);
        for(int i = 0; i < n; i ++) {
            int len = n - i;
            getNext(&str[i], len);
            for(int j = 1; j <= len; j ++) {
                int p = j;
                while(p) {
                    p = Next[p];
                    if(p && j % (j - p) == 0) {
                        int cir_num = j / (j - p);
                        ans[cir_num] = max(ans[cir_num], j);
                    }
                }
            }
        }
        ans[1] = n;
        cout << "Case #" << k << ":";
        for(int i = 1; i <= n; i ++) cout << " " << ans[i];
        cout << endl;
    }
}

四、归纳

  • 注意KMP算法算出来的循环节长度是最小循环节长度，如果需要算出所有可能循环节长度的话，就要用一个while循环一节一节往回跳+判定，由于往回跳的长度就是循环节的长度，因此实际上这是一个枚举循环节长度的过程。比如字符串aaaa，用KMP算法求出的循环节长度为1，但实际上2也是一个循环节长度，此时就要往回跳+判定来枚举全。

又WA了好久...