形式化题目

给出若干字符串，对每个字符串 $s$（$|s| = n$），求集合

即所有既是 $s$ 的前缀、又是 $s$ 的后缀的子串长度，按递增顺序全部输出。

$k = n$ 恒成立（整串与自身相等），所以答案非空；判定方式是对应位置逐字符等值。样例 ababcababababcabab 的答案是 2 4 9 18，aaaaa 的答案是 1 2 3 4 5——后者说明输出量本身可以达到 $O(n)$。

正解

思路

一句话本质：题目要的就是全部 border，而 KMP 的前缀函数 $pi$ 把所有 border 组织成一条"从最长 border 出发、反复取 $pi$"的链，沿链走一遍就能把它们全部取出来。

朴素做法为什么不行？

最直接的想法是枚举每个长度 $k$，把前 $k$ 位和后 $k$ 位逐位比较：

1
2
3for k in 1..n:
    if s[0:k] == s[n-k:n]:
        记录 k

它是对的，但每验证一个 $k$ 都要付 $O(k)$ 的代价——例如 aaaa...a 要能把整个前缀比完才确认匹配，总代价

在 $n = 4 \times 10^5$ 时约 $1.6 \times 10^{11}$ 次比较，无法通过。浪费在哪？ 每个 $k$ 被当成独立问题，可 $s[1..k]$ 本身就是 $s$ 的前缀，这些前缀的 border 之间有着强包含关系，却被完全忽略了。

把条件翻译成 border。

$s[1..k] = s[n-k+1..n]$ 说的正是"长度为 $k$ 的前缀等于长度为 $k$ 的后缀"，也就是 $k$ 是 $s$ 的 border。于是问题变成：求一个串的全部 border 长度。

KMP 只给最长 border，不够用。

$pi[i]$ 的定义是 $s[1..i]$ 的最长真 border（真 = 不等于自身），递推求它的代价是 $O(n)$。但它一次只给一个长度，而答案可能有 $n$ 个（aaaa...a 就要输出 $n$ 个长度），必须想办法把"最长"扩成"全部"。

关键性质：所有 border 构成一条链。

设 $b$ 是 $s[1..i]$ 的真 border。因为 $pi[i]$ 最长，所以 $b \leqslant pi[i]$；又 $s[1..b]$ 是 $s[1..pi[i]]$ 的前缀（长度不超过它），同时 $s[1..b]$ 也是 $s[1..i]$ 的后缀、而 $s[1..pi[i]]$ 是 $s[1..i]$ 的后缀且更长，所以 $s[1..b]$ 还是 $s[1..pi[i]]$ 的后缀。两者合起来说明 $b$ 一定是 $s[1..pi[i]]$ 的 border。

换句话说，"$s[1..i]$ 的次长 border"恰好是 $pi[pi[i]]$，再下一项是 $pi[pi[pi[i]]]$，以此类推：

即从 $pi[i]$ 出发反复取 $pi$，就枚举了全部真 border，每一步长度严格减小，链长不超过 $n$。

还差一个平凡 border。

题目要求含 $n$ 本身，而 $pi[n]$ 只是真 border（$pi[n] < n$）。所以链的起点不设为 $pi[n]$，而是直接设为 $n$：

链上除 $0$ 之外的每个值都是答案。

以样例 ababcababababcabab（$n = 18$）为例，它的 border 链如下。

graph LR
    A["18<br/>整串（平凡 border）"] --> B["9<br/>ababcabab"]
    B --> C["4<br/>abab"]
    C --> D["2<br/>ab"]
    D --> E["0<br/>空串，链终止"]

每个节点是一个 border 长度，箭头是一次 j = pi[j] 跳转。长度严格递减，走到 $0$ 说明已经没有更短的 border；链上非零节点的个数就是答案的个数。

链上的每一跳都能在 $pi$ 数组里查到：

对照表格读链：起点 $18$ 不在表内（它是平凡 border，手工补上），然后 $pi[18] = 9$、$pi[9] = 4$、$pi[4] = 2$、$pi[2] = 0$ 终止。收集到的 $18, 9, 4, 2$ 是降序的，反转后正是题目要求的 2 4 9 18。注意 $pi[18] = 9$ 而 $pi[9] = 4$，链的每一跳都来自表格中"当前长度那一列"，这是手工模拟时最容易看错的地方。

输出顺序不能忘。

回溯天然从大到小，而题目要递增，所以要翻转一次。另外从 aaaaa 可以看出，链长为 $n$ 时输出 $n$ 个数，输出量本身是 $O(n)$，实现上必须一次性拼好再写出，不能每个数字一次 I/O。

复杂度：求 $pi$ 是 $O(n)$（回退指针摊还 $O(1)$），走链是 $O(|B|) \subseteq O(n)$，总计 $O(n)$；空间 $O(n)$ 存 $pi$。

代码

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#!/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-09-30 11:53
# update_at: 2026-09-30 12:01

import sys


def prefix_function(pattern: bytes) -> list[int]:
    """pi[i] = pattern 的前 i 个字符里，最长的"既是真前缀又是真后缀"的长度。"""
    n = len(pattern)
    pi = [0] * (n + 1)
    for i in range(1, n):
        j = pi[i]                                 # 先继承上一个位置的最长 border
        while j and pattern[i] != pattern[j]:     # 失配就沿 border 链回退
            j = pi[j]
        if pattern[i] == pattern[j]:
            j += 1
        pi[i + 1] = j
    return pi


def border_chain(pi: list[int]) -> list[str]:
    """从链尾回溯得到全部 border 长度（含整串），升序返回。"""
    lengths: list[str] = []
    j = len(pi) - 1                               # 整串本身一定是一个 border
    while j:                                      # 跳到 0 说明链走完，空串不算 border
        lengths.append(str(j))
        j = pi[j]
    return lengths[::-1]                          # 回溯是降序的，翻转成题目要求的递增


def solve() -> None:
    out = [" ".join(border_chain(prefix_function(word)))
           for word in sys.stdin.buffer.read().split()]
    print("\n".join(out))


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
56
57
58
59
60
61
62
63
64
65
66
67
68/**
 * 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:31
 * update_at: 2026-10-05 02:31
 */
#include <iostream>
#include <string>

using namespace std;

typedef long long ll;

const int MAXN = 400005; // 题目给定所有字符串总长不超过 4×10^5

char s[MAXN];   // 输入串，下标从 1 开始，和题面对应
int pref[MAXN]; // pref[i] = s[1..i] 的最长真 border 长度（真 = 不等于自身）
int chain[MAXN]; // chain[1..cnt] 存当前串的全部 border 长度（回溯得到的是降序）

// 求字符串 s[1..n] 的前缀函数
void build_prefix_function(ll n) {
    pref[1] = 0;
    for (ll i = 2; i <= n; i++) {
        ll j = pref[i - 1];
        // 失配就沿 border 链回退，直到能继续匹配或退到空串
        while (j > 0 && s[i] != s[j + 1]) {
            j = pref[j];
        }
        if (s[i] == s[j + 1]) {
            j++;
        }
        pref[i] = j;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    while (cin >> (s + 1)) {
        ll n = 0;
        while (s[n + 1] != '\0') {
            n++;
        }
        build_prefix_function(n);

        // 全部 border：整串 n 是平凡 border，再沿 pref 链反复回退
        ll cnt = 0;
        ll j = n;
        while (j > 0) {
            cnt++;
            chain[cnt] = j;
            j = pref[j];
        }

        // 回溯顺序是降序的，倒着输出即为题目要求的递增顺序
        for (ll k = cnt; k >= 1; k--) {
            if (k < cnt) {
                cout << ' ';
            }
            cout << chain[k];
        }
        cout << '\n';
    }

    return 0;
}

复杂度

• 时间：$O(n)$ 求前缀函数（while 回退摊还线性）+ $O(|B|)$ 走 border 链，$|B| \leqslant n$，合计 $O(n)$；多行输入为各串长度之和的线性函数。
• 空间：$O(n)$，一个长度为 $n+1$ 的 pi 列表，另有同量级的输入/输出缓冲。

总结

本题是 KMP 前缀函数最直接的用途之一：

1. "既是前缀又是后缀"就是 border 的定义，问题转化为求全部 border。
2. $pi[i]$ 只给最长真 border，但所有 border 恰好是从它出发反复取 $pi$ 得到的一条严格递减链——这一步是整个解法的枢纽。
3. 链的起点要手工设为 $n$（补上平凡 border），链尾到 $0$ 自然终止，回溯结果反转后即为递增答案。

识别出"全部 border = $pi$ 链"这个结构之后，$O(n^2)$ 的逐位比较就变成了 $O(n)$ 的一次预处理加一次链上遍历。同一条链也是更难的 border 类题目的共同起点，例如沿链求每个前缀的最短 border、把链关系建成 border 树做统计等。