AC自动机 学习笔记

模板及讲解
解决多模板匹配文本串问题。复杂度$O(\sum len_i \times$ 字符集大小$)$
($\sum len_i$ 即为所有模式串总长(可能比Trie树大小大),字符集大小为出现的字符种类个数)
基本思想为在TrieKMP
程序主要函数:$insert$(插入单词), $find$(进行匹配), $getFail$(求失配函数)
其中$insert$(插入单词)为Trie树部分。

模板Hdu 2222:

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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
int n, sz = 500000, ch[500000 + 5][30], val[500000 + 5], tms[500000 + 5], lst[500000 + 5], f[500000 + 5], used[10000 + 5];
//n,节点时间戳,字典树数组,是否是单词, 单词出现个数,上一个单词位置(后缀链接),失配函数,该单词是否记录过
char s[1000000 + 5];
int ans;//答案
void g(int u) {//统计
if (!used[val[u]] && u) ans += tms[u], used[val[u]] = true, g(lst[u]);
//如果没有记录过并且有单词(u!=0), 则加上数量继续向下递归处理
}
void insert(char *s, int u, int ith, int a, int len) {//插入一个单词(递归更新,不建议)
int c = s[a] - 'a';
if (ch[u][c] == 0) ch[u][c] = ++sz;//新建节点
if (a == len - 1) val[ch[u][c]] = ith, tms[ch[u][c]]++; else insert(s, ch[u][c], ith, a + 1, len);
//如果是最后一个要加是单词的标记,并且注意重复的单词
}
void insert(char *s, int ith) {//插入一个单词(迭代更新,建议)
int now = 0, len = strlen(s);
for (int i = 0; i < len; i++) {
int c = s[i] - 'a';
if (!ch[now][c]) ch[now][c] = ++sz;//新建节点
now = ch[now][c];
if (i == len - 1) val[now] = ith, tms[now]++;
//如果是最后一个要加是单词的标记,并且注意重复的单词
}
}
void find(char *T) {//用字符串T当做文本串找模式串
int len = strlen(T), j = 0;//从0开始
for (int i = 0; i < len; i++) {
int c = T[i] - 'a';
j = ch[j][c];
if (val[j]) g(j); else if (lst[j]) g(lst[j]);//如果当前位置有单词或者有上一个单词(不会多余, 例子1看代码末行)则处理
}
}
void getFail() {//得到失配函数
queue<int> q;
f[0] = 0;//初始化开始点的失配函数为0
for (int c = 0; c < 26; c++) {//初始化所以与0相连的点
int v = ch[0][c];
if (v) q.push(v), f[v] = 0, lst[v] = 0;
}
while (!q.empty()) {//bfs更新
int u = q.front(); q.pop();
for (int c = 0; c < 26; c++) {
int v = ch[u][c];
if (!v) {ch[u][c] = ch[f[u]][c]; continue;} //Trie上没有这条边
q.push(v);
int j = f[u]; while (j && !ch[j][c]) j = f[j];//沿着失配边走
f[v] = ch[j][c], lst[v] = (val[f[v]]) ? (f[v]) : (lst[f[v]]);
//得到失配函数值,求出lst值
}
}
}
void clean() {//清除
for (int i = 0; i <= sz; i++) {
for (int j = 0; j < 26; j++) ch[i][j] = 0;
f[i] = lst[i] = val[i] = tms[i] = 0;
}
for (int i = 0; i <= n; i++) used[i] = false;
sz = 0;
}
void solve() {
scanf("%d", &n);
clean();
for (int i = 1; i <= n; i++) {
scanf("%s", s);
//insert(s, 0, i, 0, strlen(s));//递归
insert(s, i);//迭代
}
scanf("%s", s);
getFail(), ans = 0, find(s);
printf("%d\n", ans);
}
int main() {
int T; scanf("%d", &T);
while (T--) solve();
return 0;
}
/*
例子1:
1
2
errd
rr
errd
如果不执行该语句,rr则不能被算入
*/

常见题型
1、多模式串匹配
Q: 多模式串匹配
解: 用模式串建立AC自动机
例题: Hdu 2222
2、在AC自动机状态图上DP
Q: 有多个模式串,要求主串满足一些条件
解: 用模式串建立AC自动机,然后再AC自动机上DP
例题: Bzoj 1030

------ 本文结束 ------