KMP总结

一、字符串基础定义

• 子串：字符串中连续的一段
• 子序列：从字符串中按顺序取出若干字符（不要求连续）
• 后缀：从某位置到字符串结尾的子串，记作 $Suffix(S,i)=S[i..|S|]$
• 真后缀：不等于原串本身的后缀
• 前缀：从开头到某位置的子串，记作 $Prefix(S,i)=S[\mathrm{1..}i]$
• 真前缀：不等于原串本身的前缀
• 约定：所有字符串下标从 $1$ 开始

---

二、前缀函数（$\pi$ 数组）

定义

对于长度为 $n$ 的字符串 $s$，$\pi [i]$ 表示子串 $s[\mathrm{1..}i]$ 的最长相等真前缀与真后缀的长度：
π [ i ] = max ⁡ k = 1.. i { k : s [ 1.. k ] = s [ i − k + 1.. i ] } \pi[i] = \max_{k = 1..i} \{k : s[1..k] = s[i-k+1..i]\} π[i]=k=1..imax​{k:s[1..k]=s[i−k+1..i]}

• 若无相等，则 $\pi [i]=0$
• 规定 $\pi [1]=0$

示例

• $s=\text{"abcabcd"}$ → $\pi =[0,0,0,1,2,3,0]$
• $s=\text{"aabaaab"}$ → $\pi =[0,0,1,0,1,2,2,3]$

---

三、高效计算前缀函数（线性算法）

核心优化

1. $\pi [i+1]\le \pi [i]+1$：相邻前缀函数值至多增加 $1$
2. 当 $s[i+1]\ne s[\pi [i]+1]$ 时，跳转到 $j=\pi [\pi [i]]$，继续尝试

最终代码

vector<int> prefix_function(string s) {
    int n = (int)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;
}

• 时间复杂度：$O(n)$

---

四、KMP 字符串匹配算法

方法一：拼接法

• 构造字符串 $S^{\prime }=\text{" "}+s+\text{"\#"}+t$
• 计算 $S^{\prime }$ 的前缀函数
• 当 $\pi [i]=n$（$n$ 为模式串长度）时，找到匹配
• 匹配在文本串中的起始位置：$i-2n$

方法二：直接匹配（常用）

vector<int> find_occurrences(string text, string pattern) {
    int n = pattern.size();
    int m = text.size();
    string cur = " " + pattern + "#" + text;
    vector<int> pi = prefix_function(cur);
    vector<int> ans;
    for (int i = n + 2; i <= n + m + 1; i++) {
        if (pi[i] == n) {
            ans.push_back(i - 2 * n);
        }
    }
    return ans;
}

直接匹配写法

vector<int> kmp(string t, string s) {
    int n = s.length() - 1;  // s 为 1-indexed
    int m = t.length() - 1;
    vector<int> pi = prefix_function(s);
    vector<int> result;
    int j = 0;
    for (int i = 1; i <= m; i++) {
        while (j > 0 && t[i] != s[j + 1]) j = pi[j];
        if (t[i] == s[j + 1]) j++;
        if (j == n) {
            result.push_back(i - n);
            j = pi[j];
        }
    }
    return result;
}

• 时间复杂度：$O(n+m)$

---

五、周期与 Border

定义

• 周期：对 $0<p\le |s|$，若 $s[i]=s[i+p]$ 对所有 $i\in [1,|s|-p]$ 成立，则 $p$ 是 $s$ 的周期
• Border：若 $s$ 长度为 $r$ 的真前缀与真后缀相等，则称该前缀为 $s$ 的 border
• 关系：存在长度为 $r$ 的 border $⟺$ $|s|-r$ 是周期

重要结论

• 所有 border 长度：$\pi [n],\pi [\pi [n]],\pi [\pi [\pi [n]]],\dots$
• 最小周期 $=n-\pi [n]$

字符串压缩

设 $k=n-\pi [n]$：

• 若 $k\mid n$（$k$ 整除 $n$），则最短压缩长度为 $k$
• 否则，无法压缩，答案为 $n$

正确性说明

• 若 $k\mid n$，字符串可划分为长度为 $k$ 的若干块，所有块相等
• 若存在更小的压缩长度 $p$，则会产生比 $\pi [n]$ 更长的 border，矛盾
• 证明中使用裴蜀定理：$\gcd (k,p)$ 也是周期，且 $\gcd (k,p)<p$

---

六、统计前缀出现次数

在自身中出现

vector<int> ans(n + 1, 1);
for (int i = n; i >= 1; i--) ans[pi[i]] += ans[i];

• 最终 $ans[i]$ 表示前缀 $s[\mathrm{1..}i]$ 在 $s$ 中出现的总次数

在另一个串中出现

• 构造 $S^{\prime }=s+\text{"\#"}+t$
• 计算前缀函数，统计 $\pi [i]=|s|$ 的次数

---

七、动态维护本质不同子串数量

增量法思想

设当前字符串为 $s$，已有 $k$ 个本质不同的子串，追加字符 $c$：

1. 新子串必然是以 $c$ 结尾的后缀
2. 将 $s+c$ 反转，记反转串为 $T$
3. 原字符串中以 $c$ 结尾的新后缀 $\to$ $T$ 中的新前缀
4. 计算 $T$ 的前缀函数 $\pi$，得到最大值 ${\pi }_{\max }$
5. 新增子串数 $=(|s|+1)-{\pi }_{\max }$
6. 更新 $k\leftarrow k+((|s|+1)-{\pi }_{\max })$

算法特点

• 时间复杂度：$O(n^2)$（每次追加需 $O(n)$ 计算前缀函数）
• 可扩展到头部追加或两端删除

---

八、核心公式与结论汇总

内容	公式/结论
前缀函数定义	π [ i ] = max ⁡ k = 1.. i { k : s [ 1.. k ] = s [ i − k + 1.. i ] } \displaystyle \pi[i] = \max_{k = 1..i} \{k : s[1..k] = s[i-k+1..i]\} π[i]=k=1..imax​{k:s[1..k]=s[i−k+1..i]}
相邻关系	$\pi [i+1]\le \pi [i]+1$
失配跳转	$j=\pi [j]$
最小周期	$n-\pi [n]$
压缩条件	$(n-\pi [n])\mid n$
匹配位置（拼接法）	$pos=i-2n$