洛谷 P4391 分析（别看）

科技起源的小号1

2026-09-08 21:22:30

发布于：天津

3阅读

0回复

0点赞

原题链接

1 题目

1.1 题目所需求出内容

对于本题，最终要求：一个最小值

1.2 题目背景、允许、禁止与限制

背景：
给定一个字符串 $s$ 和其长度 $n$
允许：
求一个最短的串 $t$ 使得 $t$ 复制无数次后 $s$ 是 $tttt\cdots$ 的一个子串

1.3 题目数据范围与猜测

$1 \le l \le 10^6\longrightarrow O(n)$

1.4 一句话概括题意

求一个最短的串 $t$ 使得 $s$ 是 $t^\infty(ttt\cdots)$ 的一个子串

2 题目破题推导

其实答案就是 $n-\pi(s)$ ，其中 $\pi(x)$ 代表 $x$ 的最长公共前后缀
为什么？从两个方面说

这一段一定通过无限复制使 $s$ 是其子串

1:--------
2:   --------
 :        ---
看这里我们把这个三长度的当做是n-π(s)，姑且叫它t
会发现一个神奇的事情
t是2的最后三个=1的最后三个=2的最后4~6个（kmp算法定义保证）=1的最后4~6个=2的最后7~8个=1的最后7~8个
所以这就能保证这一段一定通过无限复制使 s 是其子串

这一段的长度 $|t|$ 一定最短

假设存在更小的周期 d' < d。

第 1 步：周期 d' 意味着什么？

如果 S 的周期是 d'，那么对于所有位置 i（1 ≤ i ≤ n-d'），都有：

$S[i] = S[i + d']$

把所有等式左边的字符拼起来，就是 S[1..n-d']；
把所有等式右边的字符拼起来，就是 S[d'+1..n]。

所以：

$S[1..n-d'] = S[d'+1..n]$

第 2 步：这跟公共前后缀有什么关系？

S[1..n-d'] 是字符串的前缀，长度是 n-d'。
S[d'+1..n] 是字符串的后缀，长度也是 n-d'。

因为它们相等，所以 S 存在一个长度为 n-d' 的公共前后缀。

第 3 步：与 π[n] 比较

π[n] 的定义是最长公共前后缀的长度。

既然已经找到了一个长度为 n-d' 的公共前后缀，那么最长的那个一定至少有这么长：

$π[n] ≥ n-d'$

第 4 步：不等式变换

$π[n] ≥ n-d'$

两边同时乘以 -1（不等号方向反转）：

$-π[n] ≤ -n + d'$

两边同时加上 n：

$n - π[n] ≤ d'$

即：

$d' ≥ n - π[n] = d$

第 5 步：得出矛盾

我们一开始假设的是 d' < d。

但推导出来的是 d' ≥ d。

矛盾！所以假设不成立，不存在比 d 更小的周期。

因此，d = n - π[n] 就是最小周期长度。

3 模型匹配

kmp模板

4 最终代码（禁止抄袭，仅用于参考）

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 10;
string s2;
int kmp[N];

int main(){

    int n;
    cin >> n;
    cin >> s2;
    int lb = s2.size();
    s2 = " " + s2;
    for (int i = 2, j = 0;i <= lb;i++){
        while(j > 0 && s2[i] != s2[j + 1]){
            j = kmp[j];
        }
        if (s2[i] == s2[j + 1]){
            j++;
        }
        kmp[i] = j;
    }
    cout << n - kmp[n];
        
    return 0;
}