DDOSvoid's Blog

AC自动机

发表于 更新于 分类于
本文字数： 4k 阅读时长 ≈ 4 分钟

简介

字符串复习计划

实际上就是 $Trie$ 树 $+$ $fail$ 指针

一般情况下为了方便匹配，将 $Trie$ 树补成了 $Trie$ 图，但有些情况下不建议这样做

为了方便我们定义 $pre[i]$ 表示 $Trie$ 上根节点到 $i$ 形成的字符串

点 $u$ 的 $fail$ 指向 $y$ 表示根到 $u$ 的这个字符串的最长的 $border$ 为根到 $y$ 这个字符串，和 $kmp$ 的 $nxt$ 数组是一样的

点 $u$ 的 $fail$ 指向 $v$ 表示 $pre[u]$ 的最长后缀是 $pre[v]$，且这个后缀是 $Trie$ 上的一个前缀，注意这个后缀不一定是 $pre[u]$ 的前缀

所以 $AC$ 自动机上的 $border$ 是区分于一般字符串的 $border$ 的，为此我们称 $pre[v]$ 为 $pre[u]$ 在 $AC$ 自动机上的 $border$

性质：

  1. $fail$ 树上 $u$ 和 $v$ 的 $lca$ 为 $pre[u]$ 和 $pre[v]$ 的公共最长 $border$

  2. $fail$ 树上，从 $u$ 到根的所有节点为 $pre[u]$ 的所有$ AC$ 自动机上的 $border$，从这一点上我们能够更加理解 $AC$ 自动机就是广义的 $KMP$

几个需要注意的事项

  1. 在 $init\underline{}fail$ 的时候，不论是建成 $Trie$ 图还是直接暴力，对 $fail$ 指针的构建是没有影响的

    但复杂度不一样，建成 $Trie$ 图 $init\underline{}fail$ 的复杂度是 $O(L*\sum)$

    而暴力跳 $fail$ 的复杂度是 $O()$ 坑，总而言之还是建成 $Trie$ 图吧

贴个板子

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
#define ch s[i] - 'a'
struct AC_automaton {
    int nxt[26], Nxt[26], cnt, fail;
} T[maxn]; int top = 1, rt = 1, id[maxn];
void insert(char *s, int k) {
    int now = rt, l = strlen(s);
    for (int i = 0; i < l; ++i) {
        if (!T[now].nxt[ch]) T[now].nxt[ch] = ++top;
        now = T[now].nxt[ch];
    } id[k] = now; 
} 

void init_fail() { // Trie 图
    queue<int> Q;
    for (int i = 0; i < 26; ++i) {
        int &u = T[rt].nxt[i];
        if (!u) { u = rt; continue; }
        T[u].fail = rt; Q.push(u); 
    }
    while (!Q.empty()) {
        int u = Q.front(); Q.pop(); 
        for (int i = 0; i < 26; ++i) {
            int &v = T[u].nxt[i];
            if (!v) { v = T[T[u].fail].nxt[i]; continue; }
            T[v].fail = T[T[u].fail].nxt[i]; Q.push(v);
        }
    }
}

void init_fail() {
    queue<int> Q;
    for (int i = 0; i < 26; ++i) {
        int u = T[rt].nxt[i]; if (!u) { T[rt].Nxt[i] = rt; continue; }
        T[rt].Nxt[i] = u; T[u].fail = rt; Q.push(u); 
    }
    while (!Q.empty()) {
        int u = Q.front(); Q.pop(); 
        for (int i = 0; i < 26; ++i) {
            int v = T[u].nxt[i];
            if (!v) { T[u].Nxt[i] = T[T[u].fail].Nxt[i]; continue; }
            T[u].Nxt[i] = v; T[v].fail = T[T[u].fail].Nxt[i]; Q.push(v);
        }
    }
}

应用

多模式串匹配

大概就是遍历文本串，然后维护 $pre[i]$ 在 $AC$ 自动机上跑的节点 $u$，然后在 $fail$ 树上前缀加

正确性的话，因为对于串 $S$ 的子串 $s$ 来说，$s$ 一定是 $S$ 的某一个前缀的后缀

而我们的 $fail$ 树上节点 $u$ 到根刚好是 $pre[u]$ 的所有 $border$

例题

AC自动机+DP

  1. 简要题意：给定 $n$ 个字符串，求是否存在一个无限长的字符串，满足不存在这 $n$ 个串中的任何一个串是其子串

    $len\le 3\times 10^4$

    简要题解：

    我们模拟文本串在匹配时所进行的操作，发现只要将 $ext$ 标记沿着 $fail$ 树下传

    然后在 $AC$ 自动机上走的时候不走有标记的点判断是否能够走一个环，有向图判环的话只需要注意回边即可

    Luogu P2444 [POI2000]病毒

AC自动机+数据结构

  1. 简要题意：给定一棵 $Trie$ 以及 $m$ 次询问，每次询问给出 $x,y$，求第 $x$ 个串在第 $y$​ 个串中出现多少次

    $len\le 10^5,m\le 10^5$

    简要题意：我们要求的就是 $fail$ 树上 $x$ 的子树内有多少点是 $y$ 的前缀节点

    我们将询问离线下来挂到 $y$​ 上，在遍历的 $Trie$​ 的过程中维护当前所在点的所有前缀节点，我们只需要将其加入到树状数组中即可，查询就是区间查询 ，时间复杂度 $O(L\log L)$​

    Luogu P2414 [NOI2011] 阿狸的打字机

  2. 简要题意：给定 $n$ 个模板串 $s_i$ 和 $m$ 个询问串 $t_i$，每次求询问串是多少模板串的子串

    $n\le 10^4,m\le 6\times 10^4,\sum |s|\le 10^5,\sum|t|\le 3.6\times 10^5$

    简要题解：我们对于询问串建立 $AC$​ 自动机

    然后考虑将模板串在 $AC$ 自动机上跑，对于模板串的每个前缀，我们都应该通过跳 $fail$ 来匹配询问串

    反过来考虑，相当于我们对于询问串求子树内不同的点的个数

    显然可以主席树，时间复杂度 $O(L\log L)$​​

    SP8093 JZPGYZ - Sevenk Love Oimaster

  3. 简要题意：有三种操作，操作一向集合中加入一个字符串，操作二从集合中删除一个字符串，操作三给定一个模板串，查询集合中的串在模板串中出现次数的总和

    $len\le 3\times 10^5$

    简要题解：首先能够想到使用 $AC$ 自动机，$AC$​ 自动机可以快速查询一系列串在模板串中的出现次数

    但是注意到题目要求动态加入和删除串，我们考虑二进制分组，合并两组的时候可以使用类似线段树合并的东西

    删除串我们可以同样看成加入，在查询时减去这些答案即可

    时间复杂度 $O(L\log^2L)$​

    CF 710F String Set Queries

  4. 简要题意：一开始现给定 $n$​ 个字符串 $S_i$​，同时有一个字符串集合 $P$​，一开始是空的，接下来有 $m$​ 次两种操作，第一种是向集合中添加一个字符串 $T$​，第二种是查询 $S_k$​ 是集合 $P$​ 中多少串的子串

    $n,m\le 10^5, \sum |S|+\sum|T|\le 2\times 10^6$

    简要题解：我们考虑对 $S$ 建立 $AC$ 自动机，每次新加入一个串 $T$，我们考虑它对于每个 $S$ 的贡献

    显然 $T$ 的每个前缀的贡献都是 $fail$ 树上的一条到根的链，那么整个串 $T$ 的贡献就是这些链的并

    求链的并有经典做法就是先将这些点按 $dfs$ 序排序，然后每个点加 $1$，$lca$​ 处减 $1$，时间复杂度 $O(L\log L)$

    Luogu P5840 [COCI2015]Divljak

  5. 简要题意：给定 $n$ 个字符串 $S_i$，$m$ 次询问 $S_k$ 在 $S_l,S_{l+1},\cdots,S_r$ 中出现的次数和

    $n,\sum|S|\le 2\times 10^5,m\le 5\times 10^5$

    简要题解：注意到 $S_k$ 的出现次数和是 $S_k$ 的结束节点的子树内的有贡献的串的前缀节点的个数和

    我们考虑离线同时将询问差分，相当于每次加入一个串的所有前缀节点，然后查询区间和，可以使用树状数组实现

    时间复杂度 $O(L\log L)$

    CF 547E Mike and Friends

  6. 简要题意：给定 $n$​​ 个字符串 $S_i$​​，$m$​​ 次询问 $S_l,S_{l+1},\cdots,S_r$​​ 在 $S_k$​ 中出现的次数和

    $n,m,\sum|S|\le 10^5$

    简要题解：注意到一次询问相当于对于 $S_k$ 的每个前缀节点求其到根的链上有多少属于 $l$ 到 $r$ 的结束节点

    或者反过来，对于 $l$ 到 $r$ 的每个结束节点求其子树内有多少 $S_k$ 的前缀节点

    我们考虑按照 $S_k$ 的长度根号分治，以 $\sqrt L$ 为界限

    对于长度大于 $\sqrt L$ 的 $S_k$​，我们考虑对于所有点求子树内有多少 $S_k$ 的前缀节点，这个离线下来可以做到单次 $O(L)$，总的时间复杂度就是 $O(L\sqrt L)$

    对于长度小于等于 $\sqrt L$​ 的 $S_k$​，我们考虑对询问差分，然后考虑离线维护前 $i$​ 个串的结束节点的贡献，然后对于 $S_k$​ 的每个前缀节点求贡献即可，注意到这里有 $O(L)$​ 次区间修改，$O(L\sqrt L)$​ 单点查询，我们根号平衡一下即可做到 $O(L\sqrt L)$​

    总的时间复杂度就是 $O(L\sqrt L)$，不过说实话感觉和带 $log$ 的差距不大

    CF 587F Duff is Mad