0%

AC自动机

本来想先讲讲自动机的概念,不过又觉得没有什么必要。理解AC自动机并不需要太多关于自动机的知识。

情景引入与分析

给出一个字典包含若干个单词,再给出一个长字符串。问在这个长字符串S中出现了多少次字典中的单词。

假设字典内有N个串,平均长度为L,长字符串长度为M。

朴素的想法,对每个单词在长字符串中查找出现了几次,时间复杂度为 O(N*(M+l)) 这还是建立在匹配用了kmp的情况下。

又考虑用字典跑出一个字典树,用S的每一位做开始进行匹配。时间复杂度 M*max(l).

其中一个可优化时间的地方就是,当匹配失效后。不应该在从S的下一位重新跑字典树,这浪费了已经匹配了若干位的已经信息。
所以考虑对已经匹配的串,找到它的最长的在字典树中存在的后缀。这里有点绕口,拆分下条件.
寻找一个串:

  1. 是已经匹配的串的后缀
  2. 这个串用在字典树上可以表示
  3. 尽可能长

这个过程与KMP非常相似,回想KMP匹配失效后寻找的是 已经匹配串的最长公共前缀后缀串,然后从这个位置开始重新匹配。
对于字典树上匹配失败,那么应当在字典的所有串中找一个 最长的前缀使得同时为已经匹配串的后缀。本质上时间上是相同的东西,不过字典中是多个串,所以是从多个串中找。

又字典树上的每个结点都代表一个串的前缀,故匹配失效后,是想找到一个节点,从那个结点继续匹配。在kmp的过程中,我们预处理出了next数组,来找到了每一个寻找关系。 在这里我们需要做的事是一样的,为每一个匹配失效的结点找一个结点。对于某节点A通过这种关系找到了B结点,我们称为A的fail指针指向B。fail指针中文名为失配指针

基本过程

建字典树

这部分和普通的字典树没有区别。
不过Node的数据多了一个表示fail指针

构建fail指针

fail的构建方法是这样的:

对于一个节点C,标识字符a,记C的父亲节点为T,T的fail指针指向S结点。
若S的子结点中存在结点P标识字符也为a,则C->fail=P;
否则 继续沿S的失配指针走,即S=S->fail

如果找不到这个节点,那么C->fail=root

在实际操作时,是用广搜来实现,因为这个建构过程要求父亲节点的失配指针已经建好,而且一层层都要建好.
另外,root的子节点一定指向root

查询

查询的部分一般要根据题意来进行修改。
不过一般的方法都是对长字符串S进行匹配,若是失配则沿当前已经匹配结点的fail指针不停跳转到新的结点,直到找到新节点的子结点可以匹配/或者一直跳到root,然后视为匹配成功。

每次匹配的成功一次后。计算当前匹配结点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
74
75
76
77
struct Trie {
static const char stdc = 'a';
int ch[N][26];
int val[N];
int num[N];
int root;
int fail[N];
int sz;
int idx(char c) {
return c - stdc;
}
void init() {
root = 0;
sz = 1;
memset(val, 0, sizeof val);
memset(num, 0, sizeof num);
memset(ch[0], 0, sizeof ch[0]);
}

void insert(char *str) {
int len = strlen(str);
int s = 0;
for (int i = 0; i < len; ++i) {
int u = idx(str[i]);
if (!ch[s][u]) {
memset(ch[sz], 0, sizeof ch[sz]);
ch[s][u] = sz++;
}
s = ch[s][u]息
num[s]++;
}
val[s]++;
}
void build() {
queue<int> Q;
fail[0] = 0;
for (int i = 0; i < 26; ++i) {
int u = ch[0][i];
if (u) {
fail[u] = 0;
Q.push(u);
}
}
while (!Q.empty()) {
int u = Q.front();
Q.pop();
for (int i = 0; i < 26; ++i) {
int r = ch[u][i];
if (!r) {
continue;
}
Q.push(r);
int v = fail[u];
while (v && !ch[v][i]) v = fail[v];
fail[r] = ch[v][i];
}
}
}
int query(char *str) {
int s = root, ans = 0;
int len = strlen(str);
for (int i = 0; i < len; ++i) {
int id = idx(str[i]);
while (s && !ch[s][id]) {
s = fail[s];
}
s = ch[s][id];
int u = s;
while (u && val[u] != -1) {
ans += val[u];
val[u] = -1;
u = fail[u];
}
}
return ans;
}
} ac;

时间复杂度分析

假设字典内有N个串,平均长度为L,长字符串长度为M。
建立Trie树:O(N*L)
建立fail指针:O(N*L)
模式匹配:O(M)
所以,总时间复杂度为:O(NL+M)。