形式化题目

给定一个长度为 $L$ 的小写字母串 $w$。已知存在某个字符串 $s$，使得 $w$ 是 $s$ 不断自我连接形成的无限串 $s^{\infty} = sss\cdots$ 的一个子串（截取起点任意，不要求对齐 $s$ 的边界）。求 $|s|$ 的最小可能值。

例如 w = $ `cabcabca` 是 `abc` 自我连接得到的 `abcabcabc` 的子串，此时 $|s| 最小为 $3$。

正解

思路

第一步：把"合法长度"翻译成"周期"。 断言：$k$ 合法（$w$ 是某长度 $k$ 的串无限自我连接后的子串）当且仅当 $k$ 是 $w$ 的周期，即 $w[i] = w[i+k]$ 对所有 $i + k < L$ 成立：

• 若 $w$ 出现在 $s^{\infty}$ 的位置 $p$ 起，那么 $w[i]$ 与 $w[i+k]$ 读的是无限串上相距 $k$ 的两个位置；$s^{\infty}$ 以 $k$ 为周期，两处字符必然相同，所以 $k$ 是 $w$ 的周期。
• 反之，若 $w[i] = w[i+k]$ 对所有 $i+k<L$ 成立，从右往左反复利用它得 $w[j] = w[j \bmod k]$，即 $w$ 恰是 $(w[0..k-1])^{\infty}$ 的长度 $L$ 前缀，当然也是其子串，$k$ 合法。

于是答案就是 $w$ 的最小周期。朴素做法：从 $k=1$ 起逐个枚举，对每个 $k$ 逐位验证上式。单次验证 $O(L)$，最坏总代价 $O(L^2)$——$L = 10^6$ 时约 $10^{12}$ 次比较，不可行。瓶颈在于各次验证互不共享信息。

第二步：用 border 对偶一步求出最小周期。 经典对偶：$d$ 是 $w$ 的周期，即 $w[i] = w[i+d]$ 对 $1 \leqslant i \leqslant L-d$ 成立，恰好说明长度 $L-d$ 的前缀 $w[1..L-d]$ 与长度 $L-d$ 的后缀 $w[d+1..L]$ 逐位相同——也就是 $L-d$ 是 $w$ 的 border（相等的真前后缀长度）；反推同样成立。因此

KMP 失配函数 $fail[i]$ 恰是前缀 $w[1..i]$ 的最长 border，一次线性扫描即可求出全部值，答案为 $L - fail[L]$。

以样例 cabcabca（$L=8$）为例，下表列出每个前缀的最长 border 与对应最小周期：行是前缀长度，前缀、border、周期各占一行，单元格为对应的具体值。

看最后一列（$i=8$）：border 长度 $5$ 说明前 5 位与后 5 位逐位相同：

1
2
3
4
5w   = c a b c a b c a      (L = 8)
pre = c a b c a            <- w[1..5]
suf =     c a b c a        <- w[4..8]，与 pre 逐位相同
           --
           位置 4..5 重叠

前缀与后缀能这样重叠，等价于整串"错位 $8-5=3$ 看还是自己"，最小周期即 $3$，也正是答案。注意整个推导只用到 $w$ 自身的结构，与 $w$ 在无限串中的截取起点无关，所以 $w$ 是否"缺一角"不影响公式。

代码

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

import sys


def longest_borders(s: bytes) -> list[int]:
    """KMP 失配函数：fail[i] = 前缀 s[:i] 的最长真 border（相等真前后缀）长度。"""
    fail = [0] * (len(s) + 1)
    k = 0  # 扫描到 i 时，k 恰好是 fail[i]
    for i in range(1, len(s)):
        while k and s[i] != s[k]:
            k = fail[k]  # 沿 border 链回退：次长 border 仍是 border
        if s[i] == s[k]:
            k += 1
        fail[i + 1] = k
    return fail


def solve() -> None:
    data = iter(sys.stdin.buffer.read().split())
    L = int(next(data))  # 题面给的字符串长度，与 len(s) 相等
    s = next(data)       # bytes：下标得到整数，字符比较更快
    fail = longest_borders(s)
    # 最短周期 = n - 最长 border，它就是能"生成"w 的最短元串长度
    print(L - fail[L])


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/**
 * 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:53
 * update_at: 2026-10-05 02:53
 */
// 求最短生成元长度：w 是某周期串的子串，等价于求 w 的最小周期。
// 由「周期–border 对偶」，最小周期 = L − 最长 border，KMP 失配函数一次线性扫描即可。
#include <iostream>
#include <string>

using namespace std;

typedef long long ll;

const int MAXN = 1000005;

ll L;      // 题面给出的字符串长度
string w;  // 待求最小周期的字符串，下标从 0 开始

int fail[MAXN]; // fail[i]：w 的长度 i 前缀的最长 border 长度；值不超过 10^6，用 int 控制内存

// KMP 失配函数：求出每个前缀的最长 border。
void build_fail() {
    fail[0] = 0;
    int k = 0; // 扫描到 i 时，k 恰好等于 fail[i]
    for (int i = 1; i < L; i++) {
        while (k > 0 && w[i] != w[k]) {
            k = fail[k]; // 沿 border 链回退：次长 border 仍是 border
        }
        if (w[i] == w[k]) {
            k++;
        }
        fail[i + 1] = k;
    }
}

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

    cin >> L >> w;

    build_fail();

    // 答案就是 w 的最小周期，也就是能自我连接生成 w 的最短元串长度
    cout << L - fail[L] << "\n";

    return 0;
}

复杂度

• 时间 $O(L)$：$fail$ 递推中 $k$ 每步至多加一，回退总次数不超过增加总次数，均摊常数次比较；相比朴素枚举的最坏 $O(L^2)$，收益正是"把重复比较换成一次求出全部 border 信息"。
• 空间 $O(L)$：失配数组与输入串。$L = 10^6$ 时实测约 55MB、0.08s。

总结

本题的全部难度在两个"翻译"：先把"$w$ 是某周期串的子串"翻译成"$k$ 是 $w$ 的周期"（合法长度集合与周期集合完全相同），再用周期–border 对偶把最小周期翻译成 $L$ 减最长 border。KMP 失配函数一次线性扫描给出最长 border，答案即 $L - fail[L]$。