【算法分析与设计】第34篇：字符串匹配的自动机理论与KMP算法
字符串匹配看似平凡，却是文本编辑器的查找替换、搜索引擎的关键词匹配、生物信息学的基因序列比对、网络入侵检测的签名匹配等无数应用的核心操作。问题定义极为简单：给定文本串 T[1..n]T[1..n] 和模式串 P[1..m]P[1..m]（m≤nm≤n），找出 PP 在 TT 中出现的所有位置。朴素算法将模式从文本的每个位置开始逐字符比对，一旦失配就右移一位重新开始，最坏情况——如 TT 全为a而 PP 为aaa...ab——需要 O(nm)O(nm) 次比较。KMP算法通过预处理模式串，利用已匹配部分的结构信息，避免了指针回溯，将总比较次数压至 O(n+m)O(n+m)。
一、确定有限自动机模型
在进入KMP算法之前，先从一个更一般的理论框架——字符串匹配自动机——出发。确定有限自动机（DFA）由五个要素构成：状态集合 QQ、输入字母表 ΣΣ、转移函数 δ:Q×Σ→Qδ:Q×Σ→Q、初始状态 q0q0 和接受状态集合 FF。
对于字符串匹配问题，自然的设计思路是：状态代表“当前已匹配的模式前缀长度”。状态 qq 表示已匹配了模式的前 qq 个字符。初始状态为 00，接受状态为 mm（匹配完整模式）。核心在于转移函数的构造：当自动机处于状态 qq（已匹配 P[1..q]P[1..q]）并读入字符 aa 时，下一个状态应是什么？
最直观的想法是：若 a=P[q+1]a=P[q+1]，则匹配延长一位，转移至 q+1q+1。若 a≠P[q+1]a=P[q+1]，则需要考虑“已匹配前缀的后缀”与“模式的前缀”的重叠情况。形式化地，设当前已匹配的字符串为 PqaPqa（PqPq 表示模式的前 qq 个字符），我们需要找到其最长的后缀，使其同时是模式 PP 的前缀。即：
δ(q,a)=max{k∣0≤k≤q+1,P[1..k] 是 (P[1..q]⋅a) 的后缀}δ(q,a)=max{k∣0≤k≤q+1,P[1..k] 是 (P[1..q]⋅a) 的后缀}
由此定义的转移函数称为后缀函数。自动机每读入一个文本字符，仅需查表一次、状态转移一次，全过程恰好扫描文本一遍，时间复杂度 Θ(n)Θ(n)。但这套方案需要一个 ∣Σ∣×(m+1)∣Σ∣×(m+1) 的转移表，当字母表较大（如Unicode）时空间开销不可接受。KMP算法正是为了克服这一缺点而设计的。
二、前缀函数：模式自匹配的精髓
KMP算法的核心预处理步骤是计算模式串的前缀函数π[1..m]π[1..m]。对每个位置 qq（1≤q≤m1≤q≤m），π[q]π[q] 定义为模式的前缀 P[1..q]P[1..q] 中最长的真前缀，使其同时也是该前缀的真后缀。形式化地：
π[q]=max{k∣0≤k<q,P[1..k]=P[q−k+1..q]}π[q]=max{k∣0≤k<q,P[1..k]=P[q−k+1..q]}
若不存在这样的 kk，则 π[q]=0π[q]=0。真前缀意味着 k<qk<q——字符串本身不算作自身的真前缀。
前缀函数的直观含义是：当匹配进行到模式位置 q+1q+1 处发生失配时，已匹配的 qq 个字符构成了文本的后缀 P[1..q]P[1..q]。我们可以利用 π[q]π[q] 得知：模式的前 π[q]π[q] 个字符恰好等于这 qq 个字符的后 π[q]π[q] 个字符。因此无需回溯文本指针，只需将模式指针跳转至 π[q]π[q] 继续比对即可——这正是KMP匹配阶段“文本指针不回溯”的根本原因。
前缀函数的计算本身是一道精巧的算法题。朴素方法对每个 qq 逐一枚举 kk 并比较字符串，复杂度 O(m3)O(m3) 或 O(m2)O(m2)。KMP利用动态规划的思想将计算压缩至 Θ(m)Θ(m)。
计算过程维护两个变量：当前待计算位置 qq（从 22 开始，π[1]=0π[1]=0），以及“候选前缀长度” k=π[q−1]k=π[q−1]。核心逻辑为：若 P[k+1]=P[q]P[k+1]=P[q]，则 π[q]=k+1π[q]=k+1，qq 递增，kk 更新为新值。若 P[k+1]≠P[q]P[k+1]=P[q]，则令 k←π[k]k←π[k]，重复此“回退”步骤，直至 k=0k=0 或匹配成功。若 k=0k=0 且 P[1]≠P[q]P[1]=P[q]，则 π[q]=0π[q]=0。
三、正确性证明与复杂度分析
前缀函数计算的正确性可通过归纳法证明。归纳假设：在计算 π[q]π[q] 之前，π[1..q−1]π[1..q−1] 已全部正确计算。算法的候选序列 k,π[k],π[π[k]],…k,π[k],π[π[k]],… 按递减顺序枚举了 P[1..q−1]P[1..q−1] 的所有满足“前 kk 个字符等于后 kk 个字符”的 kk 值。当 P[k+1]=P[q]P[k+1]=P[q] 时，找到了满足条件的最长前缀，即为 π[q]π[q]。这是正确的，因为如果有更长的满足条件的前缀，它必然在上述候选序列中且比当前 kk 更大，但算法的回退过程恰好从大到小遍历了所有候选，第一个匹配的即为最大值。
复杂度分析的关键是摊还分析。在计算过程中，kk 的值每轮迭代至多增加 11（当 P[k+1]=P[q]P[k+1]=P[q] 时 k←k+1k←k+1），而每次回退（k←π[k]k←π[k]）至少使 kk 减少 11。qq 从 22 增长到 mm，kk 总共增加不超过 m−1m−1 次，因此回退的总次数也不超过 m−1m−1。前缀函数计算的总体操作次数为 O(m)O(m)。
匹配阶段的正确性同样依赖前缀函数的性质。设文本指针为 ii，模式指针为 qq，当前已匹配 qq 个字符。当 T[i]=P[q+1]T[i]=P[q+1] 时，匹配延长，ii 和 qq 同时递增。当 T[i]≠P[q+1]T[i]=P[q+1] 且 q>0q>0 时，根据前缀函数定义，P[1..π[q]]P[1..π[q]] 是当前已匹配文本后缀的前缀，因此可安全地将 qq 设为 π[q]π[q] 继续比对，无需移动 ii。当 q=0q=0 且 T[i]≠P[1]T[i]=P[1] 时，ii 递增。文本指针 ii 从不回溯，至多移动 nn 步；qq 的减少次数受限于其增加次数（至多 nn 次），因此匹配阶段总操作次数为 Θ(n)Θ(n)。整个KMP算法——预处理加匹配——的复杂度为 Θ(m+n)Θ(m+n)。
四、自动机与KMP的内在联系
从自动机视角回看KMP，前缀函数 ππ 实质上定义了一个压缩版的自动机。完整DFA需要存储每个状态面对每个字符的转移，共 ∣Σ∣×(m+1)∣Σ∣×(m+1) 条规则。KMP的巧妙之处在于：它观察到大部分转移是平凡的——若当前字符匹配，转移至下一状态；仅在失配时才需要特殊处理，而失配处理所需的全部信息恰好编码在前缀函数 ππ 之中。状态数仍为 m+1m+1，但存储需求降至 O(m)O(m)，且与字母表大小无关。
这一洞察不仅带来了空间节省，更揭示了字符串匹配算法的本质结构：模式的自相似性（前缀与后缀的重叠）决定了匹配过程中可以安全跳过的比较次数。这一思想在后续更高级的字符串算法（如Boyer-Moore的坏字符与好后缀规则）中得到延续和发展。
五、总结与展望
KMP算法是算法设计史上的里程碑。它以 O(m+n)O(m+n) 的时间复杂度和 O(m)O(m) 的额外空间，在线性时间内解决了字符串匹配问题，且保证文本指针永不回溯——这一性质在流式输入、外部存储等无法回退的场景中具有关键价值。从自动机的理论模型出发，前缀函数将模式的结构信息压缩为轻量的跳转表，使得“失配时该跳到何处”这一问题获得了精妙的解答。
KMP是字符串精确匹配的基础算法。然而，在实际应用中，Boyer-Moore算法通过从右向左匹配和跳跃式移位，往往能跳过更多的文本字符；Rabin-Karp算法则借助哈希函数开辟了另一种完全不同的思路。而将视角从“匹配单个模式”扩展到“预处理文本以支持多模式查询”，则引出了后缀树和后缀数组等更高级的索引结构——这正是下一篇的核心主题。