KMP 字符串匹配

KMP 在文本中查找模式，失配后不回退文本游标。它先为模式构造 LPS 表，再利用已匹配部分的前后缀重叠，保留已知匹配信息。预处理 O(m)，搜索 O(n)，辅助空间 O(m)。

把模式看成放在文本下方的透明条带：失配时只移动到一个安全重叠位置，让已知相等的模式前缀对齐已匹配后缀。当前文本字符不动，LPS 表决定哪些匹配可以保留。

何时使用 KMP

普通子串查询通常调用语言内置搜索即可。文本来自不能回退的 socket、管道或文件分块，或者必须保证最坏 O(n + m) 时，KMP 有用。模式只需预处理一次，跨分块保留 j，已经读过的文本可以丢弃。

KMP 如何工作

LPS 是“最长相等真前后缀”的长度。真前缀不能是整个字符串。例如 ABABA 的最长相等真前后缀为 ABA，长度为 3。

模式每个位置都有一个 LPS 值。k 是当前要计算的位置，len 是正在尝试的边界长度。若 pattern[k] == pattern[len]，将长度加一并写入 lps[k]。若不等且 len > 0，令 len = lps[len - 1]，用更短边界重新比较同一个 pattern[k]，此时不增加 k。若已无边界，则写入 0，再增加 k。

搜索时 i 指向文本，j 指向模式。相等则两者前进；失配且 j == 0，只增加 i；失配且 j > 0，令 j = lps[j - 1]，重试同一个 text[i]。

保留 3 个字符，移动 2 格

LPS 值是保留长度，不是平移距离。j 从 5 降到 3，表示保留三个匹配字符，模式条带移动 5 - 3 = 2 格。

文本游标不后退，不代表每个文本字符只比较一次。回退模式时，i 固定，同一字符可以与多个模式位置比较。线性复杂度来自总的前进与回退次数界限。

KMP 逐步演示

默认文本为 ABABABACA，模式为 ABABACA。

1. lps[0] = 0，单字符 A 没有非空真前缀。
2. 索引 1 的 B 与 A 不同，也无更短边界，所以 lps[1] = 0。索引 2、3、4 的 A、B、A 逐次扩展重叠，得到 1、2、3。
3. 索引 5 的 C 与长度 3 边界后的字符不同。len 从 3 降到 lps[2] = 1，重试同一个 C，仍不同，再降到 lps[0] = 0，最后写入 0。重试期间索引 5 不动。
4. 索引 6 的 A 与模式首字符相同，lps[6] = 1。完整表为 [0, 0, 1, 2, 3, 0, 1]。
5. 从 i = 0, j = 0 搜索，前五对 ABABA 相等，来到 i = 5, j = 5。
6. text[5] 为 B，pattern[5] 为 C，失配。读取 lps[4] = 3，把 j 从 5 降为 3，保留 ABA，条带右移两格，i 保持 5。
7. 用同一个 text[5] 比较 pattern[3]，B 相等；后续 A、C、A 也相等。结束时 i = 9, j = 7，匹配起点为 i - j = 2。

advance i (bug) 变体只改回退分支：设置 j = lps[j - 1] 后还增加 i。这样跳过了索引 5 的 B，没能重试。真实匹配仍在索引 2，但错误代码耗尽文本后返回 -1。

时间与空间复杂度

设文本长 n、模式长 m。

预处理每轮要么增加 k，要么缩短 len；缩短总量不会超过此前增长量。搜索同样要么增加 i，要么缩短 j，而 j 的总回退距离受此前增长限制。文本游标不会重置后再完整扫描。LPS 数组占 O(m)，游标与计数器占 O(1)。

边界情况

• 空文本、非空模式：返回 -1。
• 模式比文本长：可能部分匹配，但耗尽文本后仍返回 -1。
• 单字符模式：LPS 为 [0]，搜索相当于查找该字符。
• 重复字符模式 AAAA 的 LPS 为 [0, 1, 2, 3]，后续失配可能让 i 固定而多次回退。
• 重叠匹配可利用 LPS。本实现返回第一个匹配；查找全部时，记录结果后令 j = lps[j - 1] 再继续。
• 本课拒绝空模式，因为 API 对返回约定可能不同。生产代码应先约定行为，再读取 pattern[0]。

常见错误

• 把 LPS 值当移动格数。应设置 j = lps[j - 1]，移动量是 j 的下降量。
• j > 0 回退后增加 i，漏掉当前文本字符。错误变体会漏掉索引 2 的真实匹配。
• 构造表时回退还增加 k，没有用更短边界检查当前模式字符。
• 每次失配都把 j 清零，丢弃已知重叠；若要保持正确，还必须安排好重新对齐，不能直接代替 KMP 回退。
• 把整个字符串当真前缀，这会让每个前缀都把自己当成最长边界，表失去作用。
• 声称每个文本字符只比较一次。真正的不变量是 i 不减小，且正长度回退时不增加。