KMP · prefix function / i 永不回退

KMP：用已匹配的前缀信息省掉回退

Naive matching 最浪费的地方在于：失配后明明已经比对成功了一段前缀，却把它全扔掉，文本指针退回去从头再比。KMP 的洞见是——既然失配前那段 text 就是 pattern 的某个前缀，那它内部「最长的相等前后缀」已经预先算好了，失配时直接让 pattern 指针 $j$ 跳到那里继续，文本指针 $i$ 一步都不用回退。

注 · 先认识两个概念，proper prefix（真前缀）与 proper suffix（真后缀）。一个串的 prefix 是从开头起的一段，suffix 是到结尾止的一段。冠上「真」只多一条限制：不许等于整个串本身，空串则算。

拿 abab 举例——

proper prefix:a / ab / aba（就是不含 abab 自己）
proper suffix: $b$ / ab / bab（同样不含 abab 自己）

两边都出现的最长那个是 ab。这个最长相等真前后缀的长度，正是下面要逐位算的 prefix[k]；失配时 pattern 指针就靠它知道「能直接跳到哪」。

1 · 第一步：构建 prefix function（next 数组）

prefix[k] = 子串 pattern[0..k] 里「既是它的真前缀、又是它的真后缀」的最长长度。它只看 pattern 自己，与 text 无关。点「下一步」看它怎么自底向上算出来——这是 pattern 在和自己做 KMP。

图 1-1 · prefix function 自底向上的构建过程，当前格与 len 指针同步高亮。可单步推进，看三种结局各自何时发生。

注 · 旁白里反复出现的 $len$ 指当前最长相等真前后缀候选的长度，这段相等的前后缀也叫 border；一开始它就等于上一位算好的 prefix[k-1]，接着往后用。关键在于它同时是一个下标：既然 border 长 $len$ ，想把它再延长一位，要比的就是 border 后面那个字符，而它的下标恰好是 $len$ ——所以代码里才去比 pattern[k] 和 pattern[len]。

于是每一格只有三种结局，正好对应上面旁白的三种说法：

pattern[k] == pattern[len] → border 接长一位，len+1，记 prefix[k]=len;
不等且 len>0 → 退而求其次，换更短的 border 再试： $len = prefix[len-1]$ （pattern 在和自己做回退）;
不等且 len==0 → 没有更短的可退了，这一格 prefix[k]=0。

读法：比如 pattern = ababaca，到 ababa 时 prefix=3，因为前缀 aba 同时也是它的后缀。一旦在第 6 个字符 c 处失配，我们就知道开头 3 个字符 aba 已经天然对上了，j 可以直接跳到 3 而不是 0。

2 · 第二步：用 prefix function 驱动匹配

匹配时：相等就 i、j 一起右移；失配时，若 $j>0$ 就让 j = prefix[j-1]（i 不动），否则 i 右移一格。注意看文本行——高亮会向右滑过去，但绝不会往回缩。

图 2-1 · prefix function 驱动的匹配过程。可单步推进，注意文本行的高亮只会向右滑，绝不往回缩。

建议 · $i$ 永不回退是复杂度的关键：它保证整个匹配里 text 的每个字符最多被前进读一次，总时间是 $O(n+m)$ 。Naive matching 之所以会退化到 O(n×m)，正是因为 $i$ 一次次往回退、重读同一段 text。

警示 · text 快到结尾时，有些比较是无效的。一次完整匹配要求 pattern 整个落进 text，即窗口起点 $offset = i - j$ 满足 $offset + m \le n$ （ $m$ =pattern 长， $n$ =text 长），最后一个可能的匹配起点是 $offset = n - m$ 。一旦 $offset > n - m$ （等价于「剩下的 text 比还没匹配完的 pattern 还短」），这个位置再也不可能命中。而 KMP 里 offset 是单调不减的，所以越过 $n - m$ 后可以直接终止扫描。

本页沿用教科书写法，循环只看 i < n 而不加这条提前退出——于是命中后还会把结尾那几格比一遍（默认 text 末尾的 ␣here 就是）。这不影响正确性，这些无效比较最多发生在末尾约 $m$ 个字符上、总复杂度仍是 O(n+m)；加一行 if (i − j > n − m) break; 就能省掉，代价是循环多一个分支。

3 · 换个视角：把 pattern 编译成一台 DFA

上面那套是「失配了往回退多少」（prefix 数组 + 一个内层回退循环）。Algorithms（Sedgewick）换了一种表述：既然文本指针 $i$ 永不回退，匹配过程本质上就是一台 DFA 在逐字符读文本。把「该退到哪」提前替每一个字符都算好，做成一张转移表 dfa[c][j]——搜索时每个字符只查一次表、走一步，连内层循环都没有。

注 · 状态 $j$ 表示已匹配 pattern 的前 $j$ 个字符，到达状态 $m$ 即命中；dfa[c][j] 是在状态 $j$ 读到字符 c 该跳到的状态。建表的关键是重启状态 $X$ ：它始终等于「把 pat[1..j-1] 喂进这台正在构建的 DFA 会停在的状态」。于是状态 $j$ 的失配各列可以直接抄状态 $X$ 的那一列（两者面对同一个「最长已匹配后缀」），只需再把匹配列单独改成 $j+1$ ——这正是上半页 $len = prefix[len-1]$ 那次回退，在 DFA 形式下的样子。

4 · 第三步：构建 DFA 转移表

沿用上面的 pattern。点「下一步」逐个状态（列）把表填出来：当前列高亮，旁白指出它抄自哪个重启状态。

图 4-1 · DFA 转移表逐列填出的过程，当前列高亮，表头的 ↩X 标出它抄自哪个重启状态。

5 · 第四步：用 DFA 扫描文本

表建好后，搜索就只剩 j = dfa[txt[i]][j] 一行：每读一个字符做一次转移， $i$ 永不回退、无内层循环，到达状态 $m$ 即命中。对照 §1 与 §2 那条回退链：失配该去哪，在 DFA 里早已是一条连好的边。

图 5-1 · 用建好的 DFA 扫描文本，每读一个字符做一次转移，无内层循环。到达状态

m

即命中。

prefix 数组省空间( $O(m)$ )，但失配时 $j$ 可能连续回退几次（均摊仍 $O(n)$ ）;DFA 版预处理是 $O(R\cdot m)$ （ $R$ =字母表大小），换来搜索时每个字符严格只一次转移、零再比较。二者是同一个 KMP 的两种实现形式——而「pattern 就是一台 DFA」正好接上 automata 系列：一个 pattern 本来就是最简单的正则，这张 dfa[][] 就是它的（最小）DFA。想知道这张表是怎么从 pattern 的 NFA 经子集构造「变」出来的，见「NFA / DFA 与子集构造」那页。