「笔记」AC自动机详解

AC自动机 是一个依靠 有限状态自动机 来实现的字符串搜索算法

前备知识

  1. 了解什么是 Trie 树
  2. 了解什么是 KMP 算法

AC自动机

KMP 算法是一个文本串中寻找模式串的算法,在有多个模式串时,就变得十分低效,AC自动机算法是一个文本串中查找多个模式串的算法,和 KMP 算法有异曲同工之妙,UNIX 系统中的一个命令 fgrep 就是以AC自动机算法作为基础实现的

现在重新回顾 KMP 算法的内容:如果在模式串的一个位置失配,则需要回到模式串的前面一个位置继续匹配,这个「前面一个位置」也叫做 fail 指针

跳 fail 的本质上其实是找到最长的前缀与当前后缀相等的位置

现在考虑在多个模式串的情况下考虑如何求 fail。对于多个模式串,直接考虑是自然很难的,其实可以将他们放到一颗Trie树上,便能很轻松地考虑前缀问题:

比如对于串 a, ab, ba, cc, ca, ac, cb, acb, acc 这几个串,首先建出 Trie 树:

By - Shq

考虑 dfs,显然对于节点 x 以及其父亲 f ,若 \texttt{fail}_f 有字母 x 作为子节点,那么 \texttt{fail}_x 就是 \texttt{fail}_f 的字母为 x 的子节点

若没有 x 作为子节点,则一直沿 \texttt {fail} 跳,直到跳到有 x 作为儿子的节点,比如上个图就是这样:

By - Shq

这里有一个小优化,也就是加入一个 last 表示沿着 fail 指针能走到的第一个匹配串的末尾

按照上面建AC自动机的方法其实有点慢,也就是每次沿着 \texttt{fail} 不断跳常数会很大,其实可以采用 Trie图 的方式优化,也就是无法转移的时候,在 Trie 上连向第一个可以转移的节点,这样 Trie 树就变成了 Trie 图

下面是定义、插入、建fail和查询的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
struct Node {
int ch[CHAR_SET];
int cnt;
int fail, last;
};

int tot;
Node t[MAXN];

void insert (std::string S) {
int len = S.length(), rt = 0;
for (int i = 0; i < len; i++) {
int c = S[i] - 'a';
if (!t[rt].ch[c]) t[rt].ch[c] = ++tot;
rt = t[rt].ch[c];
}
t[rt].cnt++;
}

void bfs () {
std::queue <int> q;
q.push(0);
while (!q.empty()) {
int now = q.front(); q.pop();
int k = t[now].fail;
for (int i = 0; i < CHAR_SET; i++) {
int to = t[now].ch[i];
if (!to) {
t[now].ch[i] = t[k].ch[i];
continue;
}
q.push(to);
t[to].fail = now ? t[k].ch[i] : 0;
t[to].last = t[t[to].last].cnt ? t[to].last : t[t[to].fail].last;
}
}
}

int find (std::string T) {
int ret = 0;
int len = T.length(), rt = 0;
for (int i = 0; i < len; i++) {
int c = T[i] - 'a';
rt = t[rt].ch[c];
if (t[rt].cnt) ret += t[rt].cnt, t[rt].cnt = 0;
int tmp = rt;
while (tmp) {
if (t[rt].cnt) ret += t[tmp].cnt, t[tmp].cnt = 0;
tmp = t[tmp].last;
}
}
return ret;
}

例题

模板: 【模板】AC自动机

N 个由小写字母组成的模式串以及一个文本串 T 。每个模式串可能会在文本串中出现多次。你需要找出哪些模式串在文本串TT中出现的次数最多。

AC自动机简单应用。

以及:

  1. 「JSOI2007」文本生成器
  2. 「POI2000」病毒

有限状态自动机与AC自动机

考虑开头的话:

AC自动机 是一个依靠 有限状态自动机 来实现的字符串搜索算法

十分滑稽的一点是,介绍完AC自动机了,代码也给出了,却没有介绍任何关于AC自动机所依靠的有限状态自动机

其实这个有限状态自动机就是 Trie 图(并非优化方法),也就是 Trie 数与 fail 指针。有了上面的基础,我们考虑它为什么是有限状态自动机

有限状态自动机 (Finite-State Automation,FSA)是表示 有限 个状态以及在这些状态之间的转移和动作等行为的数学计算模型:

  • \Sigma 是输入字母表(符号的非空有限集合)
  • S 是状态的非空有限集合
  • s_{0} 是初始状态,它是 S 的元素。在非确定有限状态自动机中, s_{0} 是初始状态的集合
  • \delta 是状态转移函数: \delta :S\times \Sigma \rightarrow S
  • F 是最终状态的集合, S 的子集
  1. S 是状态的非空有限集合,当自动机处于当前状态 s 时,表示 trie 树的根到状态 s 的路径上的字符与目前自动机已经接收的字符串的后缀相同,并且这个后缀尽可能长
  2. \Sigma 是 trie 树的字符集
  3. \delta 转移函数就是在自动机上加入一个节点
  4. s_0 初始状态就是 Trie 树的根
  5. F 是结束状态集合,也即 Trie 树上表示某一个串在此结束的那些点
坚持原创技术分享,您的支持将鼓励我继续创作!