6.1AC 自动机高清版本.pdf

AC自动机

主讲人：邓哲也

Trie

将若干个字符串插入Trie树。

从根节点走到任意一个叶子的路径都对应一个字符串。

下图就是插入{her,say,she,shr}的Trie树。

KMP

KMP是当用一个串去匹配另一个串的算法。

处理出的next数组，可以使得匹配失败的时候，跳过冗余

的匹配，减少多余的回溯。

bacbababaabcbab

ababaca

bacbababaabcbab

ababaca

AC自动机

当有多个模式串用来匹配时，我们可以把这些模式串都插入

Trie，然后在Trie上做匹配。

每次枚举文本串的第i位，从根开始走，如果有路就走下

去，没路就说明不能匹配上。然后从第i+1位继续。

这样的算法也会有很多冗余的匹配过程，我们可以引入KMP

中的next数组，也就是对于Trie中的每个节点，找出如

果在这个点匹配失败的话，应该跳到的下一个进行匹配的节

点，减少冗余匹配。

AC自动机

比如这颗Trie中，she中的e的next指针应该指向

her中的e。

假设文本串是sher，在匹配到she之后，可以跳到next

指针，继续匹配到her。过程中没有任何冗余匹配。

AC自动机

接下来按照BFS顺序构造每个节点的前缀指针

0

ROOT1号节点的前缀指针指向0号节点

*

定义虚拟节点0号节点，0号节点的所有连出1

的字边都连向ROOT1号节点AB

23

BAB

456

A

7

B

8

AC自动机

2号节点：

父亲是1号节点，连接字符为A，查找父亲0

的前缀指针0号节点，是否有通过A连接的*

儿子。1

AB

有！于是2号节点的前缀指针指向1号节点

23

BAB

456