最近在速通形式语言与编译，学完有限自动机（FA）后发现竟然让我自然地理解了KMP算法，和AI一番交谈后整理在此处。其实本质上就几句话，但为了更形式化，可能写得很冗长。

再次声明，本人算法水平很差，仅仅是自娱自乐。

问题背景

给定有限字母表 $\Sigma$，模式串 $P = p_1p_2\cdots p_m \in \Sigma^m$，文本串 $T = t_1t_2\cdots t_n \in \Sigma^n$。字符串匹配问题要求找出所有满足

的下标 $s$，也就是所有模式串在文本串中的出现位置。

很多人第一次学 KMP 时，会把它记成“失配时利用 next 数组回跳”。这个描述当然没错，但容易让人觉得 KMP 只是某种技巧。其实 KMP 最自然的理解方式，是把模式串看成一个确定有限自动机（DFA），然后观察 KMP 是如何用一个很小的辅助数组去压缩模拟这个自动机的。

模式串对应的 DFA

状态的定义

我们把状态集合定义为

状态 $q$ 的含义是：

当前已经读入的文本前缀的某个后缀，恰好等于模式串前缀 $P[1..q]$，并且这是最长的这样的前缀。

换句话说，状态值就是“当前已经匹配了模式串前缀的长度”。

初态为 $0$，接受态集合为

为了书写方便，约定 $P[1..0] = \varepsilon$ 为空串。

转移函数的严格定义

定义 DFA

其中转移函数 $\delta: Q \times \Sigma \to Q$ 定义为

这一定义非常关键。它说的是：

• 当前处于状态 $q$，表示我们已经掌握了后缀 $P[1..q]$
• 再读入一个字符 $a$
• 新状态就是串 $P[1..q]a$ 的后缀里，最长的、同时又是模式串前缀的长度

因此，自动机始终只保留一条信息：当前文本前缀的最长“模式前缀后缀”有多长。

AI给的定义也许过于形式化，让人难以理解，实际上的意思是，如果当前已经匹配了q个字符，再次读入一个字符(记为a)，应该转移到哪个状态。如果a依然是匹配的，那么自然转移到q+1;如果a不匹配，根据定义，转移到最长的以a结尾的后缀的长度。为了更快找到这个转移后面引入了前缀函数pi。

问题建模

设 $\delta^{*}$ 是 $\delta$ 在字符串上的自然扩展。若读完文本前缀 $T[1..i]$ 后自动机处于状态 $q_i$，那么

恰好等于满足下述条件的最大整数 $k$：

特别地，当且仅当 $q_i = m$ 时，模式串在位置 $i$ 处匹配结束。

这就是字符串匹配自动机最核心的语义。

为什么不能直接把完整 DFA 建出来

如果直接为每个状态 $q \in Q$、每个字符 $a \in \Sigma$ 预先计算 $\delta(q,a)$，时间和空间都会与 $|Q||\Sigma| = O(m|\Sigma|)$ 同阶。对理论讨论这没问题，但在实际字符串匹配里，我们通常希望预处理只和模式串长度 $m$ 成正比。

KMP 的关键思想是：

不显式存储整张转移表，而是告诉你下一个最可能的状态是什么。

比如说模式串为‘ABABABACCCDFG’当前匹配了‘ABABABA’，状态为7，而下一个读入了B，此时匹配失败应当回退，那怎么回退呢？一个自然的思路是从0到m枚举，但是观察一下会发现肯定不超过7,因为如果超过7,那么根据定义上一个状态就不应该是7。从7往下枚举，我们发现最有可能的前缀应当是‘ABABA’，然后再接上B，判断是不是正确的转移状态。而事实证明它确实是。

并且我们发现：找这个“最有可能的状态”并不依赖于我们读入的字符是什么，于是这一步就可以放在预处理里面。

这就是前缀函数（也常写作 next 数组）出现的原因。下面我们给出形式化的定义。

前缀函数与失败边

严格定义

对每个 $q \in \{1,2,\dots,m\}$，定义前缀函数

并令 $\pi(0)=0$。

也就是说，$\pi(q)$ 是字符串 $P[1..q]$ 的最长真前缀与后缀的公共长度。

这一定义只依赖模式串本身，和文本串无关。它刻画的是模式串前缀之间的自重叠结构。

自动机视角下的意义

若当前处于状态 $q$，并且读到的字符 $a$ 不能把匹配延伸到 $q+1$，那么我们就不应把所有已匹配信息全部丢掉，而应该退到一个更短但仍然可能继续匹配的状态。这个最优的回退位置正是 $\pi(q)$。

更形式化地，对 $q>0$ 有下面的递推：

同时，

这说明 $\pi(q)$ 并不是完整的转移函数，而是完整转移函数中的“失败跳转骨架”。KMP 正是靠这组失败边，在运行时动态地算出真正的字符转移。

前缀函数的构造

递推思路

设当前要计算 $\pi(i)$。假设我们已经求出了 $\pi(i-1)$，并令

这意味着 $P[1..j]$ 是 $P[1..i-1]$ 的最长后缀前缀。现在新加入字符 $p_i$：

• 如果 $p_{j+1}=p_i$，那么这个公共前后缀可以自然延长一位
• 如果 $p_{j+1}\ne p_i$，那么长度 $j$ 的候选失败，只能尝试更短的候选
• 而“下一个最长的可尝试候选”恰好是 $\pi(j)$

因此得到标准递推。

伪代码

pi[1] = 0
j = 0
for i = 2..m:
    while j > 0 and p[j+1] != p[i]:
        j = pi[j]
    if p[j+1] == p[i]:
        j = j + 1
    pi[i] = j

构造正确性的说明

在进入第 $i$ 轮循环时，变量 $j$ 保持如下不变式：

若 $p_{j+1}=p_i$，则 $P[1..j+1]$ 成为 $P[1..i]$ 的后缀前缀；若不等，则任何长度大于 $\pi(j)$ 的更短候选都已经不可能成立，因为它们必然不是 $P[1..j]$ 的后缀前缀。于是不断令 $j=\pi(j)$，最终得到的就是 $P[1..i]$ 的最长后缀前缀长度，即 $\pi(i)$。

KMP 作为 DFA 的压缩模拟

匹配过程的伪代码

j = 0
for i = 1..n:
    while j > 0 and p[j+1] != t[i]:
        j = pi[j]
    if p[j+1] == t[i]:
        j = j + 1
    if j == m:
        report(i - m + 1)
        j = pi[j]

正确性不变式

对每个 $i \in \{0,1,\dots,n\}$，在处理完文本前缀 $T[1..i]$ 后，变量 $j$ 满足

等价地，

证明可以用归纳法：

• 初始时 $i=0$，显然 $j=0$
• 假设处理完 $T[1..i-1]$ 后结论成立
• 处理字符 $t_i$ 时，若可延长，则执行 $j \leftarrow j+1$
• 若不可延长，则不断令 $j \leftarrow \pi(j)$，这正对应于沿自动机失败边回退，直到找到能够接收 $t_i$ 的状态，或退到 $0$

因此循环结束后的 $j$ 恰好等于自动机读完 $T[1..i]$ 后所在的状态。

当 $j=m$ 时，说明 $P[1..m]$ 是 $T[1..i]$ 的后缀，也就是模式串在位置 $i-m+1$ 开始出现一次。

一个例子：模式串 ababaca

设

它的前缀函数为

含义如下：

• 读到前缀 a 时，没有非空真前后缀，故为 $0$
• 读到前缀 aba 时，最长真前后缀是 a，故为 $1$
• 读到前缀 ababa 时，最长真前后缀是 aba，故为 $3$
• 读到前缀 ababac 时，最长真前后缀不存在，故回到 $0$

如果当前已经匹配到了状态 $5$，也就是后缀为 ababa，此时再读入一个不是 c 的字符，自动机不会暴力地从头开始，而是顺着失败边退到状态 $3$，因为 aba 是 ababa 的最长真前后缀。若仍不能接收该字符，再继续退到状态 $1$，必要时最终退到状态 $0$。

这正是 KMP 循环里反复执行 $j \leftarrow \pi(j)$ 的本质。

严格的复杂度分析

前缀函数预处理是 $O(m)$

观察前缀函数构造算法中的变量 $j$：

• 每次成功比较都会使 $j$ 增加 $1$
• 每次 while 循环中的回退都会使 $j$ 严格减小

在整个构造过程中，$j$ 的取值始终落在 $[0,m]$ 内。更重要的是，$j$ 的总增加次数不超过 $m-1$，因此它的总减少次数也不可能超过 $m-1$。于是 while 循环虽然看起来嵌套在 for 循环内部，但总执行次数只有 $O(m)$。

因此，前缀函数的构造时间复杂度为

空间复杂度为

匹配过程是 $O(n)$

对主匹配过程做同样的摊还分析。变量 $j$ 在整个算法中只会发生两类变化：

• 因匹配成功而自增
• 因失配而沿失败边回退

文本指针 $i$ 从左到右扫描，每次循环增加 $1$，从不回退。每次成功比较至多使 $j$ 增加一次，因此总增加次数至多为 $n$。而每次回退都使 $j$ 严格下降，所以所有回退次数的总和也至多与增加次数同阶，即为 $O(n)$。

于是匹配阶段的总时间复杂度为

额外空间复杂度为

（若不计已经存好的 $\pi$ 数组）。

综合起来，KMP 的总复杂度是

这里有一个常见误解：虽然某个固定的文本位置 $i$ 处，模式指针 $j$ 可能连续回退多次，但这些回退不会在每个 $i$ 上都重新付一遍。因为每回退一次，都意味着此前某处一定发生过一次增长；增长总数是线性的，所以回退总数也是线性的。

直觉总结

如果只看表面动作，KMP 像是在做“失配后回跳”。但从有限自动机角度看，它其实是在做一件更干净的事：

1. 用状态 $q$ 表示“当前文本后缀和模式前缀的最长匹配长度”
2. 用 DFA 的转移函数描述读入新字符后的最优状态更新
3. 用前缀函数 $\pi$ 记录失败边，从而避免显式存储整张转移表
4. 在运行时顺着失败边回退，动态算出真正的状态转移

所以，KMP 并不是“某种神奇的跳跃技巧”，而是：

对模式匹配 DFA 的一种线性时间、线性预处理、低空间的压缩模拟。

一旦从这个角度理解它，next 数组就不再像一个需要死记硬背的公式，而是自动机失败边的自然编码。