djwj233 的博客

djwj233 的博客

AC 自动机 学习笔记

posted on 2021-10-27 19:57:43 | under 笔记 |

什么是 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。

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

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

  • 注意:整张字典图不一定是 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

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,然后树上统计。

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

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

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

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

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

Code

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

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

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

调了快一天Code