题目链接

算法竞赛进阶指南-55.周期

一个字符串的前缀是从第一个字符开始的连续若干个字符，例如 abaab 共有 $5$ 个前缀，分别是 a，ab，aba，abaa，abaab。

我们希望知道一个 $N$ 位字符串 $S$ 的前缀是否具有循环节。

换言之，对于每一个从头开始的长度为 $i$（$i>1$）的前缀，是否由重复出现的子串 $A$ 组成，即 $AAA…A$ （$A$ 重复出现 $K$ 次,$K>1$）。

如果存在，请找出最短的循环节对应的 $K$ 值（也就是这个前缀串的所有可能重复节中，最大的 $K$ 值）。

输入格式

输入包括多组测试数据，每组测试数据包括两行。

第一行输入字符串 $S$ 的长度 $N$。

第二行输入字符串 $S$。

输入数据以只包括一个 $0$ 的行作为结尾。

输出格式

对于每组测试数据，第一行输出 Test case # 和测试数据的编号。

接下来的每一行，输出具有循环节的前缀的长度 $i$ 和其对应 $K$，中间用一个空格隔开。

前缀长度需要升序排列。

在每组测试数据的最后输出一个空行。

数据范围

$2 \le N \le 1000000$

输入样例：

3
aaa
4
abcd
12
aabaabaabaab
0

输出样例：

Test case #1
2 2
3 3

Test case #2

Test case #3
2 2
6 2
9 3
12 4

Method : KMP

$nxt[i]$的含义：对于字符串的前缀子串$S[0, i]$，$nxt[i]$是该前缀子串所有相等的前后缀里长度的最大值。

令$T = n - nxt[n]$，则$T$是最小循环节，并且如果$T\nmid n$，则题目无解。

证明1：$T$是一个最小循环节。

反证法：假设$\exists T' < T$，
那么有$n - T' > n - T = nxt[n]$，与$nxt[n]$是所有相等的前后缀里长度的最大值这一点矛盾。

证明2：如果字符串中存在更大的循环节$T'$，则$T'$必然是$T$的整数倍，即$T \mid T'$。

反证法：假设$\exists T' > T$，且$T \nmid T'$,
那么设$d = gcd(T, T')$，易知$d \mid T$，因此$d < T$。
由裴蜀定理，可知$d = xT + yT'$成立，不妨假设$x > 0, y < 0$，那么对于原字符串$S$：
$\forall i\in n, S_i = S_{i + T} = S_{i + 2 T} = ... S_i+xT = S_{i + xT -T'} = S_{i + xT - 2T'} = S_{i + xT - yT'} = s_{i + d}$
得到$S_i = S_{i + d}$，由定义可知$d$是一个循环节，又因为$d < T$，与$T$是最小循环节矛盾。

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1e6 + 7;

int n;
string s;

vector<int> get_next(string& p) {
    int m = p.size();
    
    vector<int> nxt(m);
    nxt[0] = -1;
    for (int i = 1, j = -1; i < m; i ++) {
        while (~j && p[i] != p[j + 1]) j = nxt[j];
        if (p[i] == p[j + 1]) j ++;

        nxt[i] = j;
    }
    
    return nxt;
}

int main() {
    int T = 1;
    while (scanf("%d", &n), n) {
        cin >> s;
        
        vector<int> nxt = get_next(s);
        
        printf("Test case #%d\n", T ++);
        for (int i = 1; i < n; i ++) {
            int t = i - nxt[i];
            if (t != 0 && (i + 1) % t == 0 && (i + 1) / t > 1) {
                printf("%d %d\n", (i + 1) , (i + 1) / t);
            } 
        }
        puts("");
    }
    return 0;
}

复杂度分析

• 时间复杂度：${O(2n)}$， 其中$2n$为函数$get\_next()$的时间复杂度。

• 空间复杂度：${O(n)}$，$nxt$ 数组实际上只用了$O(n)$的空间。

证明参考：https://www.acwing.com/video/4635/