信竞学习笔记：AC 自动机
AC 自动机是在 Trie 字典树采用 KMP 思想匹配多个模式串的一种自动机。
AC 自动机在 Trie 字典树上维护一个 fail 数组。fail_u 代表走到节点 u 但下一字符无法继续匹配时还能继续匹配的后缀节点。建立 fail 数组通常采用 BFS。
struct AC {
int ch[N][30]; // 字典树
int fail[N], cnt[N];
int tot;
}
在如上的结构体中，ch_{u,c} 代表从节点 u 通过字符 c 能走到哪个节点；fail_u 代表节点 u 的失配指针；cnt_u 代表以节点 u 作为结尾的模式串的个数。
void insert(string s) {
int u = 0;
for (const char &c : s) {
int x = c - 'a';
if (!ch[u][x]) ch[u][x] = ++tot;
u = ch[u][x];
}
cnt[u]++;
}
如上代码展示了如何将一个字符串插入 AC 自动机中，与 Trie 字典树模板基本相同。
void build() {
queue<int> q;
for (int c=0; c<26; c++) {
int v = ch[0][c];
if (v) {
fail[v] = 0;
q.push(v);
}
}
while (!q.empty()) {
int u = q.front();
q.pop();
for (int c=0; c<26; c++) {
int v = ch[u][c];
if (v) {
fail[v] = ch[fail[u]][c];
q.push(v);
}
else ch[u][c] = ch[fail[u]][c];
}
}
}
如上代码展示了建立 fail 数组的过程。首先，遍历一遍字符集，找出与根节点有连边的字符，将其 fail 值赋值为根节点（因为与根节点相连可以从根节点重新匹配），并将这一层的节点压入队列。随后，进行 BFS：每次遍历到一个点，当有其他点与当前点有边相连，则修改 fail 数组，否则修改 ch 数组，让当前节点向失配节点的对应节点指过去。
int find(string s) {
int u = 0, ans = 0;
for (const char &c : s) {
u = ch[u][c-'a'];
int x = u;
while (x) {
ans += cnt[x];
x = fail[x];
}
}
return ans;
}
如上代码是朴素的查找方式。考虑极端情况：当字典树退化成一条链，且待匹配串的字符都在链上，时间复杂度会退化。因此，我们要考虑优化：
void build() {
queue<int> q;
for (int c=0; c<26; c++) {
int v = ch[0][c];
if (v) {
fail[v] = 0;
q.push(v);
}
}
while (!q.empty()) {
int u = q.front();
q.pop();
for (int c=0; c<26; c++) {
int v = ch[u][c];
if (v) {
fail[v] = ch[fail[u]][c];
cnt[v] += cnt[fail[v]]; // 修改处
q.push(v);
}
else ch[u][c] = ch[fail[u]][c];
}
}
}
void find(string s) {
int u = 0, ans = 0;
for (const char &c : s) {
u = ch[u][c-'a'];
ans += cnt[u]; // 修改处
}
return ans;
}
这样优化，通过预处理 cnt 数组再累加的方式，可以避免上述链结构带来的影响。