KMP · prefix function / i 永不回退

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

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

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

拿 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。

旁白里反复出现的 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 右移一格。注意看文本行——高亮会向右滑过去，但绝不会往回缩。

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。点「下一步」逐个状态（列）把表填出来：当前列高亮，旁白指出它抄自哪个重启状态 X（表头标 ↩X）。

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

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

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