字符串匹配与前缀函数（KMP）

一句话定义

字符串匹配在长为 n 的文本中定位长为 m 的模式串：朴素法 O(nm)；KMP 预处理模式串构造前缀函数（prefix/failure/next 数组，O(m)），使匹配阶段文本指针永不回退，总复杂度 O(n+m)；Rabin-Karp 则用滚动哈希以期望 O(n+m) 完成多模式场景。

为什么重要

文本搜索是最高频的计算之一（编辑器、日志分析、入侵检测、DNA 序列比对）。KMP 是「用预处理换主循环零回退」思想的教科书案例，其前缀函数还是 AC 自动机（多模式）、Z 函数、字符串周期性判定（最小循环节）的共同地基——学透它，字符串这一族就打开了。

前置知识

kp-022（双指针不回退思想）；kp-006（字符数组）；前后缀概念。

核心概念

• 前缀函数 π[i]：s[0..i] 的「最长相等真前后缀」长度（真 = 不能是整个串）。
• π 的含义：失配时模式串应滑到哪里——已匹配的后缀若同时也是前缀，这部分无需重比。
• 构造 π（O(m)）：双指针，k 为当前候选前缀长；失配则沿 π 链回退 k = π[k−1]，直至匹配或归零。
• 匹配阶段（O(n)）：文本指针只前进；失配时模式串指针沿 π 链回退（均摊 O(n)）。
• 周期性推论：n − π[n−1] 是最小周期；若整除 n 则串由该周期循环构成。
• 同族算法：Z 函数（与 π 可互推）；Rabin-Karp（滚动哈希 + 碰撞二次验证，天然适配多模式）；Boyer-Moore（坏字符/好后缀，文本子串跳跃，工程最快）；AC 自动机（KMP 的 trie 版，多模式一次扫完）。

直观类比

朴素匹配像「每次失配都把模式串退回起点、文本也倒回去」，KMP 像「失配时利用刚刚读过的记忆」：已匹配部分的尾巴和头长得一样（相等前后缀），把模式串滑到让这段「自我重叠」对齐即可，文本的读头一个字符都不用倒带——记忆（π 数组）就是效率。

原理与机制

构造 π 的伪代码（KMP 的全部难点在此）：

函数 buildPi(p):
    π[0] ← 0
    k ← 0                       // 当前相等前后缀长度
    对于 i 从 1 到 m−1:
        当 k > 0 且 p[i] ≠ p[k]: k ← π[k−1]   // 沿失败链回退
        若 p[i] == p[k]: k ← k + 1
        π[i] ← k
    返回 π
匹配:
    k ← 0
    对于 i 从 0 到 n−1:
        当 k > 0 且 t[i] ≠ p[k]: k ← π[k−1]
        若 t[i] == p[k]: k ← k + 1
        若 k == m: 输出命中起点 i − m + 1 ; k ← π[k−1]

为什么是线性：i 每步至多 +1，k 的回退都对应此前某次 +1（势能论证），两阶段合计 O(n+m)。正确性核心：π[k−1] 给出「次长的相等前后缀」，沿链回退穷尽所有候选。

图示

模式串 ababaca 的 π 数组：

下标:   0  1  2  3  4  5  6
字符:   a  b  a  b  a  c  a
π:      0  0  1  2  3  0  1
解释: 到 'ababa'(下标4) 为止，最长相等真前后缀是 "aba"，长 3。
失配在 c 时（已匹配 6 个），模式串滑到使前缀 "aba" 对齐已匹配尾 "aba"，
文本指针不动，从 c 的位置继续比较。

实例或案例

• 编辑器/grep 的单模式搜索底层思想（工程实现多用 BM/混合，但 KMP 是理解它们的门槛）。
• 判断字符串是否由某个子串循环构成：(n − π[n−1]) 整除 n 即是（LeetCode 459）。
• 日志中匹配攻击特征串、垃圾邮件规则：多模式用 AC 自动机（KMP 的 trie 推广）。
• 生物信息 DNA 序列 ACGT 串的最小周期与重复片段分析。

常见误区

• π 数组定义版本混乱（有的书存「下一匹配位置」、有的存「最长长度」）：先钉死定义再写代码，本库用「最长长度」口径。
• 认为 KMP 实测一定快于朴素法：小模式/小文本时预处理与分支开销占优，朴素法反而更快；KMP 的价值在最坏界与流式场景。
• Rabin-Karp 不做二次字符验证：哈希碰撞会误报，命中处仍需逐字符确认。
• 把 π 链回退写成 k = π[k]（差一错误）：应为 π[k−1]。

自测题

1. 手算 abab 与 aabaab 的 π 数组。

答案要点：abab → [0,0,1,2]；aabaab → [0,1,0,1,2,3]。

1. 为什么匹配阶段文本指针永不回退仍不会漏解？

答案要点：失配时已匹配后缀中与模式前缀相等的部分（π 链）被自动对齐，所有可能的下一次起点都在链上被覆盖，归纳可得无遗漏。

1. 如何用 π 判断字符串 s 的最小周期？

答案要点：L = n − π[n−1]；L 为最小周期，若 L 整除 n 则 s 由周期循环构成。

与其他知识点的关系

kp-022 的「指针不回退」思想在此字符串化；kp-009 的哈希思想衍生 Rabin-Karp；kp-031 无直接关联但 AC 自动机的计数常用状压（kp-028）；kp-006 数组寻址是所有字符处理的底座。

延伸阅读

Knuth–Morris–Pratt 1977 论文；《算法导论》第 32 章（32.4 KMP 与 32.2 Rabin-Karp）；CP-Algorithms 的 Prefix Function 条目。