# MP、KMP 与 AC 自动机

> 来源：IDS 课件第 25–62 页。统一把“状态”解释为已匹配的前缀长度；具体 next/fail 数组下标可与课件不同。

## 1. 先会读字符串

文本 T 是被搜索的数据，模式 P 是要找的特征。n 是文本长度，m 是模式长度；前缀从开头取，后缀从末尾取，子串是连续的一段。

例：`P=abab` 的真前缀有空串、a、ab、aba；真后缀有空串、b、ab、bab。“真”表示不能取整个字符串。

蛮力算法在每个候选起点逐字符比较，最坏 `O(nm)`。改进算法的核心是利用已经匹配过的信息，避免无意义重比。

## 2. MP 的失败链接

已经匹配的串为 q，失配后不用从零重新开始；寻找 q 的**最长真后缀，同时也是 P 的前缀**，保留这段已有匹配。

```text
已匹配 ababa，下一字符不能延伸
ababa 的最长真前后缀是 aba
可退回“已匹配 aba”的状态，而不是让文本倒退
```

失败链接针对已匹配前缀，不是“随便找模式里相同的字符”。文本指针不需回头，状态沿 fail 回退。

## 3. 用一张前缀表手算

约定 pi[i] 为 `P[0..i]` 的最长相等真前后缀长度：

| i（从0起） | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| P=ababaca | a | b | a | b | a | c | a |
| pi[i] | 0 | 0 | 1 | 2 | 3 | 0 | 1 |

若已匹配 k 个字符后失配，常用回退写法是 `k=pi[k−1]`，继续试当前文本字符；k=0 且仍不匹配才消耗该文本字符。

有的资料用 next[0]=−1，有的把状态编号当数组下标；不要把不同定义的数值表直接混用。

## 4. KMP 相对 MP 的 Knuth 优化

若在已匹配长度 k 时，当前输入 c 已知不等于 `P[k]`，回退到 j 后又有 `P[j]=P[k]`，则比较 c 与 P[j] 一定还失败，可以继续跳过这个状态。

例：P=`ababaca`，在 k=3 时期待 b，但输入不是 b；普通 fail 退到 k=1，该状态也期待 b，因此可直接再退，避免重复确定会失败的比较。

MP 与 KMP 都可达到 `O(n+m)`。教材和代码中也常把基于前缀函数的常见写法统称 KMP；考试若强调两者区别，就说明这里的跳过优化。

## 5. 为什么总回退次数仍是线性的

匹配状态随成功扩展最多增长 O(n) 次；每次失败回退使状态长度减少，不能无限减少而不先增长，因此总回退量也是 O(n)。这叫均摊分析，不是说每个字符只发生一次比较。

## 6. AC 自动机：同时找多个模式

AC 是 MP 思路的多模式扩展：

| 结构 | 作用 |
|---|---|
| Trie / follow 边 | 合并各模式公共前缀 |
| fail 链 | 找当前串最长的、仍是某模式前缀的真后缀 |
| output | 报告当前位置匹配到哪些完整模式 |

Trie 的一个节点代表一个模式前缀；根表示空串。

## 7. 用课件模式集合演示

模式集合 `{her,iris,he,is}`。

```text
根
├─ h ─ e [he] ─ r [her]
└─ i ─ r ─ i ─ s [iris]
     └─ s [is]
```

上图是前缀树示意；节点 i 的两条分支分别到 ir 与 is。

- fail(he)=根：没有非空后缀同时是这些模式前缀。
- fail(iri)=i：其后缀 i 是模式前缀。
- fail(iris)=is：其后缀 is 是模式前缀。
- 到达 iris 节点时要报告 iris，同时报告 fail 链上的 is。

为什么要 output 继承？同一个结束位置可能对应多个长度不同的模式，漏掉 fail 链输出就会漏检。

## 8. 构造与匹配

先插入所有模式形成 Trie，再按深度从浅到深（常用 BFS）计算 fail，最后准备输出信息。匹配时，存在所需字符边就走；没有就沿 fail 找，直到能走或回根。

设总模式长度 M、命中次数 occ。课件在固定字母表等适当实现假设下给出构造 O(M)、搜索 `O(n+occ)`。若用平衡树等存转移，要计入查询代价；若输出很多命中，本来就需要时间把它们报告出来。

填全每个状态每种字符的转移可获得直接查表的 DFA 风格实现，但会增加空间。速度与内存是设计权衡。

## 自测

1. 模式 aa、aaa，文本 aaa，一共多少次出现？——aa 两次，aaa 一次，共三次，可重叠。
2. fail 是否总指向父节点？——不是，父节点删最后字符，fail 找最长可用后缀。
3. AC 的 O(n+occ) 为什么包含 occ？——必须报告所有匹配结果。
