AC 自动机 学习笔记

· · 个人记录

什么是 AC 自动机

AC 自动机（Aho-Corasick automaton，abbr. ACAM），诞生于贝尔实验室。

AC 自动机是一种多模匹配算法，就是解决 多个模式串 匹配 单个/多个 文本串用的。

之后的复杂度分析均用 s_i 代表模式串，t_i 代表文本串。

AC 自动机的主过程

以P3808 【模板】AC自动机（简单版）为例。

看到有很多个模式串，自然想到建一棵 Trie 树，那么建了 Trie 树之后我们就从头开始尽可能地向下走。

要是往下匹配走到头了怎么办呢？我们考虑借用一个 KMP 的思想，从当前节点跳到它的最长的在 Trie 中的真后缀，这样就可以继续匹配了。

具体地，我们对每个结点定义一个 \text{fail} 指针，指到当前结点最长的在 Trie 中的真后缀。

那么怎么求出这个 \text{fail} 指针呢？只需要和 KMP 一样不停地向前跳就可以了，这样就在 \mathcal O(\sum|s_i|) 的时间内完成了建树。

具体实现时，由于 \text{fail} 的长度一定小于原串的长度，我们可以用一个 BFS 的过程完成。

Code：

void build()
{
    fo(i,0,25) if(trie[0][i]!=0)
        q.push(trie[0][i]);
    while(q.size())
    {
        int x=q.front().x; q.pop();
        fo(i,0,25) {
            if(trie[x][i]!=0) {
                fail[trie[x][i]] = trie[fail[x]][i];
                q.push(trie[x][i]);
            } else {
                trie[x][i] = trie[fail[x]][i];
            }       
        }
    }
}

可以发现，我们把 \text{fail} 指针直接并在了原先的 Trie 中，这样形成的一个数据结构叫作字典图。

证明：树边显然是 DAG，而每条非树边总是从一个字符串连向它的一个真后缀。

这样随便反证一下就证完了。

回到这道题，这道题统计答案时可以直接暴力跳 \text{fail}，跳到某个结点就打一个 -1 的 tag，就做完了。

可以发现，复杂度是 \mathcal O(\sum|s_i|+n|\Sigma|+|T|)，其中 |\Sigma| 代表字符集的大小。

OI - Wiki 中说如果不建字典图并且避免跳到空结点就可以去掉 n|\Sigma|，不过貌似没啥用。

Code：

#include<bits/stdc++.h>
using namespace std;
#define fo(v,a,b) for(int v=a;v<=b;v++)
#define fr(v,a,b) for(int v=a;v>=b;v--)
#define il inline

const int N=5000010;

int n, len; char s[N];
int cnt[N], trie[N][26], tot, fail[N];

void insert()
{
    len=strlen(s+1);
    int p=0;
    fo(i,1,len) {
        if(trie[p][s[i]-'a']==0)
            trie[p][s[i]-'a']=(++tot);
        p = trie[p][s[i]-'a'];
    } cnt[p]++;
}

queue<int> q;

void build()
{
    fo(i,0,25) if(trie[0][i]!=0)
        q.push(trie[0][i]);
    while(q.size())
    {
        int x=q.front(); q.pop();
        fo(i,0,25) {
            if(trie[x][i]!=0) {
                fail[trie[x][i]] = trie[fail[x]][i];
                q.push(trie[x][i]);
            } else {
                trie[x][i] = trie[fail[x]][i];
            }       
        }
    }
}

int query()
{
    int p=0, ans=0; len=strlen(s+1);
    fo(i,1,len) {
        p = trie[p][s[i]-'a'];
        for(int j=p; j&&cnt[j]!=-1; j=fail[j])
            ans+=cnt[j], cnt[j]=-1;
    } return ans;
}

int main()
{
    cin>>n;
    fo(i,1,n) {
        scanf("%s",s+1);
        insert();
    } build();

    scanf("%s",s+1);
    printf("%d\n",query());

    return 0;
}

Record

例题

尝试在 ACAM 上匹配自己。

你发现只要建出 ACAM，然后尝试把每个字符串作为文本串做一遍。

当然也可以有一种更精妙的做法，就是统计每个结点在几个字符串中出现过，这样每个结点的权值就是其子树内值的和。

代码懒得打。

你发现你好像不太会做。

后来你发现不会出现一个单词是另一个单词子串的情况，于是你就秒了。

具体地，这个性质保证了如果两个字符串中的一个开始位置小，那么它的结束位置也小。

这样就可以在 ACAM 上乱搞了，具体实现时可以考虑维护一个栈，然后记录每个位置对应的结点。

Code

Fail 树

这题严格不弱于P3796 【模板】AC自动机（加强版）。

先说 P3796 这个 Easy version。这道题中，我们建好 ACAM 后，直接暴力往上跳 \text{fail} 就能过。

void query()
{
    int p=0, len=strlen(s+1);
    fo(i,1,len) {
        p = trie[p][s[i]-'a'];
        for(int j=p; j; j=fail[j])
            if(id[j]!=-1) cnt[id[j]]++;
    }
}

Code

但是我们发现查询的复杂度非常不行。

比如我们取 s=\{\texttt{a},\texttt{aa},\texttt{aaa},\texttt{aaa},\cdots\}，然后 t=\mathtt{aaa\cdots a}，模拟一下过程发现这个查询被我们卡到了平方级别。

P5357 卡掉了这一暴力，那么怎么做呢？

我们发现，所有的贡献都是在 \text{fail} 指针上完成的，而所有 \text{fail} 指针连的边形成一个 DAG，这样我们就可以考虑拓扑排序。

但是，有一种更为通用、简洁的打法，那就是 Fail 树。

具体地，我们把除了根节点以外所有点的 Fail 指针倒着连。

这样，由于每个点只会有一个 Fail 指针，因此这样形成的图是以 0 为根的树。

证明：显然。

这样就可以把字符串题转化成一个图论问题了。

比如在这道题中就等价于求出每个结点的子树中的贡献，直接一遍 DFS 即可。

Code

一道好题。我们依照题意建出 ACAM，这样得到一棵树。

然后我们发现：字符串 x 在 y 中的出现几次，y 就有恰好几个前缀在 \text{fail} 树中是 x 的一个后代。

显然要离线。我刚开始想要离线 x 一维，然后得到了一个 DSU + BIT + ACAM 上树剖的巨大多 \mathcal O(n\log^3 n) 做法，觉得我是煞笔。

然后考虑离线 y 一维，然后你就会了复杂度 \mathcal O(n\log n) 的做法。

具体地，我们 DFS 整棵 \text{fail} 树，然后记录每个点的 DFS 序。再 DFS 一遍 Trie，然后用和树剖类似的做法统计贡献。

Code

注意：这种数子串一般都考虑 ACAM，是从子串处计算子树贡献。

AC 自动机配合 DP

这种问题的特征是得到的字符串中 能/不能 出现模式串中的任何一个，一般复杂度都是 *ACAM 结点数 字符串长度** 的。

看到这个极小的数据范围，显然 DP。

我们对每个结点，预处理出有 cnt_i 个字符串是它的后缀，然后设 dp_{i,j} 为长度为 i，以结点 j 结尾的最大值。

有转移：dp_{i,x}=dp_{i-1,fa_x}+cnt_i。然后用 dp_{i,x} 去更新 dp_{i,fail(x)}。这个 DP 过程可以用树上 DP 实现。

Code

简单容斥。Code

就是在上面那题基础上加了一个数位 DP。Code

例题

有一个比较 nb 的题单，挑了几道题出来。

我们先建出一棵 ACAM，我们发现结点不合法，当且仅当它在 \text{fail} 树中没有被打过 tag 的祖先。

之后我们发现存在一种无穷串合法，当且仅当 ACAM 中存在一个合法环，那么我们 DFS 这个 ACAM，找环就可以了。

直接交过不去 hack：1 0，解决方法可以在刚开始把根节点的左右儿子建好。

Code

我们考虑对点名串建 ACAM，然后树上统计。

到如果直接建字典图，复杂度会爆炸，那么我们可以开 STL map，建图时不建出整张字典图，在匹配失败时直接跳 \text{fail} 即可。

这样我们把题目转化成这样一个东西：

给一棵树，Q 次询问，每次询问给出一个点集 S，求 S 中所有点到根的路径中包含的点的并集大小。

然后我就不会简单做法了。。。硬刚的话会一个倍增+树状数组的 2log 做法，可能过不了。

然后就看题解，发现了一种 nb 做法，就是对这个点集按 DFS 序排序然后相邻项 LCA。

Code

数据结构题。无论题怎么改，这种区间问题一定要想到线段树、分块！！！

然后如果我们考虑建线段树，空间复杂度会爆炸，所以我们考虑分块。

回忆一下区间加、区间推平的维护，就是在每个块上维护加法、推平 tag，然后散块修改时直接下传。

调了快一天Code

还是考虑建出 ACAM，然后我们发现 s_i 和 s_j 符合题意当且仅当 s_j 不在 s_i 中有过被别的串包含的出现。

倒序枚举 s_j 的右端点在 s_i 中的出现，如果前一次合法的出现没有包含这一次就把它加上。

注意：这里如果直接 ans++ 是错的，因为它可能在后面被覆盖。

因此我们需要检查每个出现过的 j 的出现次数是否等于它不被覆盖的出现次数。

Code