形式化题目

给定一个长度为 $k$ 的小写字母字符串 $S$。

对于 $S$ 的任意前缀 $A$：

• 若存在一个真前缀 $Q$（即 $Q \neq A$ 且 $Q$ 非空），使得 $A$ 是字符串 $QQ$ 的前缀，则称 $Q$ 是 $A$ 的一个周期。
• $A$ 的最大周期定义为 $A$ 的所有周期中最长的那一个；若 $A$ 不存在任何周期，则其最大周期为空串（长度为 $0$）。

求字符串 $S$ 的所有非空前缀的最大周期长度之和。

正解

思路

1. 周期与 Border 的对偶转化

设当前考虑的前缀为 $A$，其长度为 $|A| = i$。假设 $Q$ 是 $A$ 的一个周期，长度为 $|Q| = q$。

根据定义：

1. $Q$ 是 $A$ 的真前缀，因此 $1 \le q < i$。
2. $A$ 是 $QQ$ 的前缀。因为 $q < i \le 2q$，字符串 $QQ$ 的长度为 $2q$。
   • $QQ$ 的前 $q$ 个字符构成了 $Q$，而后 $q$ 个字符同样是 $Q$。
   • $A$ 作为 $QQ$ 的前缀，其长度为 $i$。因此 $A$ 的后缀（从位置 $q + 1$ 到 $i$，长度为 $i - q$）必然等于 $Q$ 的前缀（长度为 $i - q$）。
   • 又因为 $Q$ 本身是 $A$ 的前缀，所以 $Q$ 的前 $i - q$ 个字符也就是 $A$ 的前 $i - q$ 个字符。
   • 这意味着：$A$ 拥有一个长度为 $b = i - q$ 的公共真前缀与真后缀（即 Border）。

反过来，如果 $A$ 拥有一个长度为 $b$（$1 \le b < i$）的 Border，那么取 $q = i - b$：

• 由于 $b \ge 1$，有 $q < i$，即 $Q = A[1 \dots q]$ 是 $A$ 的真前缀；
• 由于 $b < i$，有 $q > 0$；
• 此时 $QQ$ 的前 $i$ 个字符刚好与 $A$ 匹配，即 $A$ 是 $QQ$ 的前缀。

因此，$Q$ 是 $A$ 的周期 $\iff$ $A$ 存在长度为 $i - |Q|$ 的 Border。

2. 最大周期与最短 Border

题目要求求出 $A$ 的最大周期长度 $\max(q)$。由等式 $q = i - b$ 可知：

• 如果 $A$ 不存在任何正长度的 Border，则 $A$ 没有任何周期，最大周期长度计为 $0$。
• 如果 $A$ 存在 Border，则 $A$ 的最大周期长度等于 $i$ 减去 $A$ 的最短正 Border 长度。

3. 利用 KMP失配树与路径压缩

在 KMP 算法中，前缀函数（next 数组）记录的是每个前缀的最长非平凡 Border 长度。 根据 Border 的传递性，前缀 $A$ 的所有 Border 长度依次为：

若每次暴力沿着 $nxt$ 链跳转到底部，单次最坏退化为 $O(i)$，总时间复杂度会退化为 $O(n^2)$。

我们可以采用路径压缩（记忆化递推）： 记 $\text{min\_border}[i]$ 为前缀 $S[1 \dots i]$ 的最短正 Border 长度。

• 若 $nxt[i] = 0$，说明前缀 $i$ 没有 Border，$\text{min\_border}[i] = 0$。
• 若 $nxt[i] > 0$：
  • 如果子前缀 $nxt[i]$ 自身已有最短正 Border（即 $\text{min\_border}[nxt[i]] > 0$），则前缀 $i$ 直接继承它：$\text{min\_border}[i] = \text{min\_border}[nxt[i]]$；
  • 否则说明 $nxt[i]$ 自身就是最底层的非平凡 Border，直接取 $\text{min\_border}[i] = nxt[i]$。

这样每个状态只需 $O(1)$ 时间即可转移，总复杂度线性。

代码

Python 版：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-07-05 21:47
# update_at: 2026-07-05 21:47

import sys


def compute_next(s: str, n: int) -> list[int]:
    """计算 KMP 的 next 数组（nxt[i] 表示前缀 s[:i] 的最长非平凡 border 长度）。"""
    nxt = [0] * (n + 1)
    j = 0
    for i in range(1, n):
        while j > 0 and s[i] != s[j]:
            j = nxt[j]
        if s[i] == s[j]:
            j += 1
        nxt[i + 1] = j
    return nxt


def solve() -> None:
    data = iter(sys.stdin.buffer.read().split())
    n = int(next(data))
    s = next(data).decode()

    nxt = compute_next(s, n)

    # min_border[i] 记录前缀 s[:i] 的最短正 border 长度；
    # 路径压缩记忆化：若其 next 指向的子前缀已有最小 border 则直接继承，否则为其自身。
    min_border = [0] * (n + 1)
    total_period = 0
    for i in range(1, n + 1):
        if nxt[i] > 0:
            min_border[i] = min_border[nxt[i]] if min_border[nxt[i]] else nxt[i]
            total_period += i - min_border[i]

    print(total_period)


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 02:52
 * update_at: 2026-10-05 02:52
 */

// KMP 求所有前缀的最大周期长度之和：
// 前缀 A(长度 i) 的周期 Q(长度 q) <=> A 有长度 b = i - q 的正 border，
// 所以最大周期 = i - 最短正 border。沿 next 失配链 + 路径压缩 O(n) 求出。

#include <cstdio>
#include <cstring>

typedef long long ll;

const int MAXN = 1000005;

int n;                      // 串长
char s[MAXN];               // 输入串，下标从 1 开始
int nxt[MAXN];              // KMP 失配数组：nxt[i] = 前缀 s[1..i] 的最长非平凡 border 长度
int min_border[MAXN];       // min_border[i] = 前缀 s[1..i] 的最短正 border 长度（0 表示没有）

int main() {
    scanf("%d", &n);
    scanf("%s", s + 1);

    // 求 next 数组
    nxt[1] = 0;
    int j = 0;
    for (int i = 2; i <= n; i++) {
        while (j > 0 && s[i] != s[j + 1]) j = nxt[j];
        if (s[i] == s[j + 1]) j++;
        nxt[i] = j;
    }

    // 路径压缩求每个前缀的最短正 border：
    // 若 nxt[i] 自己已有更短的 border 就继承，否则 nxt[i] 就是最短的
    ll ans = 0;
    for (int i = 1; i <= n; i++) {
        if (nxt[i] == 0) {
            min_border[i] = 0; // 没有任何 border，最大周期为空串
        } else {
            if (min_border[nxt[i]] > 0)
                min_border[i] = min_border[nxt[i]];
            else
                min_border[i] = nxt[i];
            ans += i - min_border[i]; // 最大周期长度 = i - 最短正 border
        }
    }

    printf("%lld\n", ans);
    return 0;
}

复杂度

• 时间复杂度：$O(n)$。预处理 KMP 的 next 数组耗时 $O(n)$；随后进行一次线性扫描，通过已计算的 min_border 数组 $O(1)$ 转移并累加答案，总耗时为 $O(n)$。
• 空间复杂度：$O(n)$。需要存储原字符串以及长度为 $n + 1$ 的 next 数组与 min_border 数组。

总结

本题的关键在于通过数学观察将「求最大周期 $Q$」对偶转化为「求最短正 Border $b$」。借助 KMP 算法的失配指针链结构以及记忆化/路径压缩技巧，避免了沿失配树向上暴跳的退化风险，将求解过程优化至严格的 $O(n)$ 线性时间。