来源: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 的前缀,保留这段已有匹配。
已匹配 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}。
根 ├─ 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 风格实现,但会增加空间。速度与内存是设计权衡。
自测#
- 模式 aa、aaa,文本 aaa,一共多少次出现?——aa 两次,aaa 一次,共三次,可重叠。
- fail 是否总指向父节点?——不是,父节点删最后字符,fail 找最长可用后缀。
- AC 的 O(n+occ) 为什么包含 occ?——必须报告所有匹配结果。