AC 自动机

很多人在第一次看到这个东西的时侯是非常兴奋的。不过这个自动机叫作 Automaton,不是 Automation,这里的 AC 也不是 Accepted,而是 Aho–Corasick(Alfred V. Aho, Margaret J. Corasick. 1975)。

前置

Trie (字典树)

KMP (只要失配指针的思想即可)

定义

AC 自动机是 以 Trie (字典树) 的结构为基础,结合 KMP (字符串匹配) 的思想 建立的自动机,用于解决多模式匹配等任务。

构建

先简单解释一下:

AC 自动机由两部分组成:

  1. 将模式串构造成一棵普通的 Trie。

  2. 利用 KMP 思想构造失配指针。

失配指针

同 KMP 一样,AC 自动机同样构造一个 fail 用于失配时的跳转指针。

但 AC 自动机的 fail 指向当前状态的最长后缀。

定义如下变量:

当前节点 uu 的父亲节点 ppu 间用一条字符 c 连接。

字典树的边集 tr。(\(tr[u][c]\) 表示节点 uc 出边的点)

假设所有深度小于 u 的 fail 指针均已求得。

  1. \(tr[fail[p]][c]\) 存在,则让 \(fail[u]=tr[fail[p]][c]\)

  2. 否则,找到 \(fail[fail[p]]\),重复 1 的过程,直到根节点。

  3. 如果还没有,令 \(fial[u]=root\)。(\(root\) 表示根节点)

自动机

AC 自动机通过 一个 BFS 函数实现 fail 和 自动机 的构建。

定义如下变量:

字典树的边集 tr。(\(tr[u][c]\) 表示节点 uc 出边的点)

  1. 将根节点的所有子节点入队。

  2. 对于队头 u,遍历字符集,设当前遍历到 i

    1. \(tr[u][i]\) 存在,则将 \(fail[tr[u][i]]=tr[fail[u]][i]\)

    2. 否则,令 \(tr[u][i]=tr[fail[u]][i]\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
queue<int> q;
void build() {
for (int i = 0; i < 26; i++)
if (nd[0].son[i]) q.push(nd[0].son[i]);
while (!q.empty()) {
int u = q.front();
q.pop();
for (int i = 0; i < 26; i++)
if (nd[u].son[i])
nd[nd[u].son[i]].fail = nd[nd[u].fail].son[i], q.push(nd[u].son[i]);
else
nd[u].son[i] = nd[nd[u].fail].son[i];
}
}

匹配

遍历文本串 T,设当前点为 u

  1. 利用 fail 找到所有匹配的模式串,累加,清零。
1
2
3
4
5
6
7
8
9
10
int query(char *t) {
int u = 0, sum = 0;
for (int i = 1; t[i]; i++) {
int c = t[i] - 'a';
u = nd[u].son[c];
for (int j = u; j && nd[j].e != -1; j = nd[j].fail)
sum += nd[j].e, nd[j].e = -1;
}
return sum;
}

例题

P3808 AC 自动机(简单版)

直接套 AC 自动机。

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
#include <queue>
#include <stdio.h>
using namespace std;
const int N = 1e6 + 5;
int n;
struct AC {
int cnt;
struct node {
int son[30], fail, e;
} nd[N];
void insert(char *s) {
int u = 0;
for (int i = 1; s[i]; i++) {
int c = s[i] - 'a';
if (!nd[u].son[c]) nd[u].son[c] = ++cnt;
u = nd[u].son[c];
}
nd[u].e++;
}
queue<int> q;
void build() {
for (int i = 0; i < 26; i++)
if (nd[0].son[i]) q.push(nd[0].son[i]);
while (!q.empty()) {
int u = q.front();
q.pop();
for (int i = 0; i < 26; i++)
if (nd[u].son[i])
nd[nd[u].son[i]].fail = nd[nd[u].fail].son[i], q.push(nd[u].son[i]);
else
nd[u].son[i] = nd[nd[u].fail].son[i];
}
}
int query(char *t) {
int u = 0, sum = 0;
for (int i = 1; t[i]; i++) {
int c = t[i] - 'a';
u = nd[u].son[c];
for (int j = u; j && nd[j].e != -1; j = nd[j].fail)
sum += nd[j].e, nd[j].e = -1;
}
return sum;
}
} ac;
char s[N];
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%s", s + 1), ac.insert(s);
ac.build();
scanf("%s", s + 1);
printf("%d\n", ac.query(s));
return 0;
}

P3796 AC 自动机(简单版 II)

基本思路一样。

多记录两个东西:

  1. 每个模式串在字典树中结束的位置

  2. 每个字典树上的点匹配到模式串的次数

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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <cstring>
#include <queue>
#include <stdio.h>
using namespace std;
const int N = 156, T = 1e6 + 6, S = N * 80;
struct AC {
int cnt, ans[N];
struct node {
int son[30], fail, idx, val;
} nd[S];
void init() {
memset(nd, 0, sizeof nd);
memset(ans, 0, sizeof(ans));
cnt = 0;
}
void insert(char *s, int id) {
int u = 0;
for (int i = 1; s[i]; i++) {
int c = s[i] - 'a';
if (!nd[u].son[c]) nd[u].son[c] = ++cnt;
u = nd[u].son[c];
}
nd[u].idx = id;
}
queue<int> q;
void build() {
for (int i = 0; i < 26; i++)
if (nd[0].son[i]) q.push(nd[0].son[i]);
while (q.size()) {
int u = q.front();
q.pop();
for (int i = 0; i < 26; i++)
if (nd[u].son[i])
nd[nd[u].son[i]].fail = nd[nd[u].fail].son[i], q.push(nd[u].son[i]);
else
nd[u].son[i] = nd[nd[u].fail].son[i];
}
}
int query(char *t) {
int u = 0, sum = 0;
for (int i = 1; t[i]; i++) {
int c = t[i] - 'a';
u = nd[u].son[c];
for (int j = u; j; j = nd[j].fail) nd[j].val++;
}
for (int i = 0; i <= cnt; i++)
if (nd[i].idx) sum = max(sum, nd[i].val), ans[nd[i].idx] = nd[i].val;
return sum;
}
} ac;
int n;
char s[N][100], t[T];
int main() {
while (scanf("%d", &n)) {
if (n == 0) break;
for (int i = 1; i <= n; i++)
scanf("%s", s[i] + 1), ac.insert(s[i], i);
ac.build();
scanf("%s", t + 1);
int x = ac.query(t);
printf("%d\n", x);
for (int i = 1; i <= n; i++)
if (ac.ans[i] == x) printf("%s\n", s[i] + 1);
ac.init();
}
return 0;
}

优化

在 AC 自动机中,会一直跳 fail 寻找匹配,但这样效率极低。

考虑优化:

先考虑 fail 的特性:一定是一棵树。

而我们 AC 自动机的匹配就可以转化为在 fail 树上的链求和问题。

这里提供两种思路。

例题:P5357 【模板】AC 自动机

拓扑优化(快)

考虑预先记录所有跳的 fail,最后一并求和。

于是按照 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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include <queue>
#include <stdio.h>
using namespace std;
const int N = 2e5 + 5, S = 2e5 + 5, T = 2e6 + 5;
char s[S], t[T];
int n;
struct AC {
int cnt = 1, ans[N], f[N], in[N];
struct node {
int son[27], fail, f, ans;
} nd[N];

queue<int> q;

void insert(char *s, int id) {
int u = 1;
for (int i = 1; s[i]; i++) {
int c = s[i] - 'a';
if (!nd[u].son[c]) nd[u].son[c] = ++cnt;
u = nd[u].son[c];
}
f[id] = (nd[u].f) ? nd[u].f : nd[u].f = id;
return;
}

void build() {
for (int i = 0; i < 26; i++) nd[0].son[i] = 1;
nd[1].fail = 0;
q.push(1);
while (!q.empty()) {
int u = q.front();
q.pop();
int fail = nd[u].fail;
for (int i = 0; i < 26; i++) {
int v = nd[u].son[i];
if (!v) {
nd[u].son[i] = nd[fail].son[i];
continue;
}
nd[v].fail = nd[fail].son[i], in[nd[fail].son[i]]++;
q.push(v);
}
}
}

void topsort() {
for (int i = 1; i <= cnt; i++)
if (!in[i]) q.push(i);
while (!q.empty()) {
int u = q.front();
q.pop();
ans[nd[u].f] = nd[u].ans;
int fail = nd[u].fail;
nd[fail].ans += nd[u].ans;
if (!--in[fail]) q.push(fail);
}
}

void query(char *s) {
int u = 1;
for (int i = 1; s[i]; i++) u = nd[u].son[s[i] - 'a'], nd[u].ans++;
}
} ac;

int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%s", s + 1), ac.insert(s, i);
ac.build();
scanf("%s", t + 1);
ac.query(t), ac.topsort();
for (int i = 1; i <= n; i++) printf("%d\n", ac.ans[ac.f[i]]);
return 0;
}

子树求和(慢)

先子树求和,最后累加。

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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include <deque>
#include <stdio.h>
using namespace std;
typedef deque<int> dq;
const int N = 2e5 + 5, S = 2e5 + 5, T = 2e6 + 5;
int n;
char s[S], t[T];
int cnt[N];
struct ACM {
struct node {
int son[30], val, fail, hd;
dq idx;
} nd[S];
struct edge {
int to, nt;
} e[S];
int rt, acnt, tot;
void insert(char *s, int id) {
int u = rt;
for (int i = 1; s[i]; i++) {
int c = s[i] - 'a' + 1;
if (!nd[u].son[c]) nd[u].son[c] = ++acnt;
u = nd[u].son[c];
}
nd[u].idx.push_back(id);
}
void build() {
dq q;
for (int i = 1; i <= 26; i++)
if (nd[rt].son[i]) q.push_back(nd[rt].son[i]);
while (!q.empty()) {
int u = q.front();
q.pop_front();
for (int i = 1; i <= 26; i++)
if (nd[u].son[i]) {
nd[nd[u].son[i]].fail = nd[nd[u].fail].son[i];
q.push_back(nd[u].son[i]);
} else
nd[u].son[i] = nd[nd[u].fail].son[i];
}
}

void query(char *s) {
int u = rt;
for (int i = 1; s[i]; i++) {
int c = s[i] - 'a' + 1;
u = nd[u].son[c], nd[u].val++;
}
}

void add(int u, int v) { e[++tot] = {v, nd[u].hd}, nd[u].hd = tot; }

void dfs(int x) {
for (int i = nd[x].hd; i; i = e[i].nt) {
int v = e[i].to;
dfs(v);
nd[x].val += nd[v].val;
}
for (auto i : nd[x].idx) cnt[i] += nd[x].val;
}

void failtr() {
for (int u = 1; u <= acnt; u++) add(nd[u].fail, u);
dfs(rt);
}
} ac;

int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%s", s + 1);
ac.insert(s, i);
}
ac.build();
scanf("%s", t + 1);
ac.query(t), ac.failtr();
for (int i = 1; i <= n; i++) printf("%d\n", cnt[i]);
return 0;
}

后记

这篇文章是近半年未写算法后的第一篇文章,很不容易,希望大家多支持。

参考 : AC 自动机 - OI Wiki