2026-05-03
1 前缀函数
1.1 定义
对于长度为 n 的字符串 s，前缀函数 \(π_i\) 定义为：
子串 s 中最长的 相等的真前缀与真后缀 的长度。
示例：
s = a b c a b c d
π = 0 0 0 1 2 3 0
1.2 暴力求法
直接枚举所有可能并逐一比较：
时间复杂度 \(O(n^3)\)
2 高效求法
2.1 优化一：相邻 π 值最多增加 1
当 \(s_{i+1} = s_{π_i+1}\) 时，\(π_{i+1} = π_{i} + 1\)
否则 \(π_{i+1} ≤ π_{i}\)，需要回退寻找更短的公共前后缀
2.2 优化二：失配时利用 π 跳转
当 \(s_{i} != s_{j+1}\) 时，不是简单地将 j 减 1，而是直接跳到 \(j = π_{j}\)
点击查看 $O(n)$ 解法
vector <int> prefix(string s){int n=s.length();vector <int> pi(n+5);for(int i=2;i<=n;i++){int j=pi_{i-1};while(j>0&&s_{i}!=s_{j+1})j=pi_{j};if(s_{i}=s_{j+1})j++;pi_{i}=j;}return pi; }复杂度：
while 循环的总回退次数不会超过总增加次数，故整体为 \(O(n)\)
3 KMP
3.1 拼接法
- 构造新串：
S = " " + pattern + "#" + text，其中#是分隔符
- 计算
S的前缀函数：当在 text 部分出现 \(π_{i} = n\)，找到一个匹配。
- 匹配在 text 中的起始位置：
\(i - 2n\)
4.2 直接匹配法
不实际拼接，用双指针在 text 上移动：
vector<int> kmp(string t, string s) {int j = 0; // j 表示模式串当前已经匹配的长度for (int i = 1; i <= m; i++) { // i 遍历文本串while (j > 0 && t[i] != s[j + 1]) j = pi[j];if (t[i] == s[j + 1]) j++;if (j == n) { // 成功匹配！j = pi[j];}}return result; }两种方法本质相同，都依赖 π 数组避免暴力回溯
4. 周期与 Border
- 周期 p：对所有 \(i\) 满足 \(s_{i} = s_{i+p}\)，则称 p 为周期。
- Border：长度为 \(r\) 的前缀等于长度为 \(r\) 的后缀。
- 关系：
字符串有长度为 \(r\) 的 \(border \Leftrightarrow |s| - r\) 是周期。
由 π 的定义知，最长 border 长度 = \(π_{n}\)，因此 最小周期 = \(n - π_{n}\)。
所有 border 可沿 π 回溯得到： \(π_{n}, π_{π_{n}}, π_{π_{π_{n}}} ...\)
4.1 字符串压缩
给定 \(s\)，求最短的字符串 \(t\) 使得 \(s\) 是 \(t\) 的多次重复拼接
令 \(k = n - π_{n}\)：
- 若 \(n % k = 0\)，则 \(t\) 的长度为 \(k\)
- 否则不存在更短的压缩，答案为 \(n\)
时间复杂度 \(O(n^2)\)