AC自动机学习笔记

字数统计: 2.2k字 | 阅读时长: 10分

RT，我学习了AC自动机。本文会介绍一些AC自动机的基本姿势，不会咕。

AC自动机简介

AC自动机是一个用来解决多个字符串匹配的高效算法，传说AC自动机需要掌握trie和kmp，亲测只会trie、完全不懂kmp的傻子也可以理解。

经典应用，判断多个单词是否在一个字符串中出现。

介绍一下它的原理，如果用单纯的trie来解决这个问题，在一个单词匹配完毕的时候，我们会回到trie树的根匹配下一个子串，这就很不优，如果我们能跳到下一个相同字符，并且单词前缀和当前单词后缀相同的位置，就能继续匹配了。

fail指针就是用来完成这个任务的，如果在某节点x匹配字符i失败，我们的指针就要到达t[x].fail处继续匹配，否则就去匹配t[x].ch[i]。

上一张全网都在用的例图，图中的虚线就是fail指针的指向。

我们发现：fail指针只能指向深度比当前浅的点（退而求其次），如果没有符合要求的点就会指向根（GG）。

fail指针的求法：递推，用bfs先把比一个点深度小的点的fail指针全求出来。对于一个点x，如果它的字符为i，那么我们看看$t[t[x].fa].fail$的儿子中有没有i，有的话就是$t[x].fail=t[t[t[x].fa].fail].ch[i]$ ，否则就一直找下去一直到根。

话是这么说，但是一般写起来不是用暴力模拟我刚刚说的话，而是用一种被dalao称为“补trie图”的做法。

先看代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void build(){
    head=tail=1; team[head]=0;
    while (head<=tail){
        int x=team[head];
        for (int i=0; i<26; i++){
            if (x==0){
                if (t[x].ch[i]){
                    team[++tail]=t[x].ch[i];
                    t[t[x].ch[i]].fail=0;
                }
                continue;
            }
            if (t[x].ch[i]){
                team[++tail]=t[x].ch[i];
                t[t[x].ch[i]].fail=t[t[x].fail].ch[i];
            }
            else t[x].ch[i]=t[t[x].fail].ch[i];
        }
        head++;
    }
}

首先，对于根的儿子，他们的fail就是根，入队就完了。

对于其他点，他们的fail就是$t[t[x].fail].ch[i]​$，那么问题来了，要是没有这个点呢？不应该往上跳吗？

不然，看这句：$else\ t[x].ch[i]=t[t[x].fail].ch[i];$

如果这个点不存在，那$t[t[x].fail].ch[i]$的值就是$t[t[t[x].fa].fail].ch[i]$

再没有就是$t[t[t[t[x].fa].fa].fail].ch[i]$，祖祖辈辈无穷尽也，一直到根的儿子这个值会是0,0是根的编号。

快乐一发：$t[t[t[t[t[t[t[t[t[x].fa].fa].fa].fa].fa].fa].fa].fail].ch[i]$

之后就是查询了，对于每一位我们只关心他是不是单词的末尾。

所以就可以一直跳fail指针就好了，看代码。

1
2
3
4
5
6
7
8
for (int i=0; i<l; i++){
    int a=ch[i]-'a';
    u=t[u].ch[a];
    for (int j=u; j&&t[j].cnt!=-1; j=t[j].fail){
        ans+=t[j].cnt;
        t[j].cnt=-1;
    }
}

这样我们就解决了洛谷上AC自动机的第一道模板题。传送门

一些其他操作

fail树

例题 传送门

统计每个单词的出现次数，有不少人的写法就是这样（选自某yyb大佬的题解）：

1
2
3
4
5
6
7
8
int l=s.length();
int now=0,ans=0;
for(int i=0;i<l;++i)
{
    now=AC[now].vis[s[i]-'a'];//向下一层
    for(int t=now;t;t=AC[t].fail)//循环求解
         Ans[AC[t].end].num++;
}

但这个会慢是因为每一位都跳到了根，然而没有必要这样做。

以样例为例

每个点有且只有一个fail指针，而根不算fail指针，将fail指向的点看成自己的爸爸，这样就形成了一棵fail树。

我们暴力统计的时候，每到达一个点是一个单词的末尾，就给这个单词出现次数+1，同时给这个点到根的所有是单词末尾的点都+1。

这样我们只要打好标记，结束后求一遍每个点的子树和，就可以知道他被打了多少次标记了。

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
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
struct tree{
    int ch[26],cnt,fail;
}t[100001];
struct node{
    int next,to;
}w[150001];
int n,num,pos[200],sum[150001],heap,tail;
int head[150001],team[105001],cnt,maxn;
char ch[200][100],s[1000010];
inline void add(int x,int y){
    w[++cnt].next=head[x];
    w[cnt].to=y; head[x]=cnt;
}
inline void insert(int x){
    int u=0,l=strlen(ch[x]);
    for (int i=0; i<l; i++){
        int a=ch[x][i]-'a';
        if (!t[u].ch[a]) t[u].ch[a]=++num;
        u=t[u].ch[a];
    }
    t[u].cnt++; pos[x]=u;
}
inline void build(){
    heap=tail=1; team[heap]=0;
    while (heap<=tail){
        int x=team[heap];
        for (int i=0; i<26; i++){
            if (x==0){
                if (t[x].ch[i]){
                    t[t[x].ch[i]].fail=0;
                    team[++tail]=t[x].ch[i];
                }
                continue;
            }
            if (t[x].ch[i]){
                t[t[x].ch[i]].fail=t[t[x].fail].ch[i];
                team[++tail]=t[x].ch[i];
            }
            else t[x].ch[i]=t[t[x].fail].ch[i];
        }
        heap++;
    }
}
void dfs(int x){
    for (int i=head[x]; i; i=w[i].next){
        dfs(w[i].to); sum[x]+=sum[w[i].to];
    }
}
int main(){
    while (1){
        scanf("%d",&n);
        if (!n) return 0; num=0;
        memset(t,0,sizeof(t));
        memset(ch,0,sizeof(ch));
        memset(pos,0,sizeof(pos));
        memset(sum,0,sizeof(sum));
        memset(head,0,sizeof(head));
        for (int i=1; i<=n; i++){
            scanf("%s",ch[i]);
            insert(i);
        }
        build(); scanf("%s",s); cnt=0;
        for (int i=1; i<=num; i++){
            add(t[i].fail,i);
            // printf("%d %d\n",t[i].fail,i);
        }
        int u=0,l=strlen(s);
        for (int i=0; i<l; i++){
            int a=s[i]-'a';
            u=t[u].ch[a];
            sum[u]++;
        }
        dfs(0); maxn=0;
        for (int i=1; i<=n; i++)
            maxn=max(maxn,sum[pos[i]]);
        printf("%d\n",maxn);
        for (int i=1; i<=n; i++)
            if (sum[pos[i]]==maxn) printf("%s\n",ch[i]);
    }
    return 0;
}

AC自动机上DP

例题

一般这种dp都是两维，$f(i,j)$表示匹配到第i个字符，在ac自动机的第j个位置的答案，第一维一般可以滚动。一个状态能转移到它的子节点或fail指针。

这道题还要复杂一点，$f(i,j,p,z)$表示匹配到第i个字符，在ac自动机第j个位置，卡上界情况是p，前导零情况是z。枚举四维之后枚举0到9转移即可，有一些小细节自行注意。

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
#include<cstdio>
#include<cstring>
#include<iostream>
#define mod 1000000007
using namespace std;
struct node{
    int cnt,ch[10],fail,val;
}t[1501];
int num,ans,f[2][1501][2][2];
int head,tail,team[1501],m,r;
char ch[1501],n[1201];
inline void insert(char *s){
    int u=0,l=strlen(s);
    for (int i=0; i<l; i++){
        int a=s[i]-'0';
        if (!t[u].ch[a]) t[u].ch[a]=++num;
        t[num].val=a; u=t[u].ch[a];
    }
    t[u].cnt=1;
}
inline void build(){
    head=tail=1;
    while (head<=tail){
        int x=team[head];
        for (int i=0; i<=9; i++){
            if (!x){
                if (t[x].ch[i]){
                    t[t[x].ch[i]].fail=0;
                    team[++tail]=t[x].ch[i];
                }
                continue;
            }
            if (t[x].ch[i]){
                t[t[x].ch[i]].fail=t[t[x].fail].ch[i];
                team[++tail]=t[x].ch[i];
            }
            else t[x].ch[i]=t[t[x].fail].ch[i];
        }
        head++;
    }
}
int main(){
    scanf("%s",n+1); r=strlen(n+1);
    scanf("%d",&m);
    for (int i=1; i<=m; i++){
        scanf("%s",ch);	insert(ch);
    }
    build(); f[0][0][1][0]=1;
    for (int v=0; v<=r-1; v++){
        int i=v%2,u;
        for (int j=0; j<=num; j++){
            for (int p=0; p<=1; p++)
                for (int z=0; z<=1; z++){
                if (!f[i][j][p][z]) continue;
                for (int k=0; k<=9; k++){
                    if (k==0&&!z){
                        f[i^1][0][0][0]=(f[i^1][0][0][0]+f[i][j][p][z])%mod;
                        continue;
                    }
                    if (p&&n[v+1]-'0'==k){
                        if (t[j].ch[k]){
                            if (t[t[j].ch[k]].cnt) break;
                            u=t[j].ch[k],f[i^1][u][1][1]=(f[i^1][u][1][1]+f[i][j][p][z])%mod;
                        }
                        else{
                            u=t[t[j].ch[k]].fail;
                            if (!t[u].cnt)
                                f[i^1][u][1][1]=(f[i^1][u][1][1]+f[i][j][p][z])%mod;
                        }
                        break;
                    }
                    if (t[j].ch[k]){
                        if (t[t[j].ch[k]].cnt) continue;
                        f[i^1][t[j].ch[k]][0][1]=(f[i^1][t[j].ch[k]][0][1]+f[i][j][p][z])%mod;
                    }
                    else{
                        u=t[t[j].ch[k]].fail;
                        if (!t[u].cnt)
                            f[i^1][u][0][1]=(f[i^1][u][0][1]+f[i][j][p][z])%mod;
                    }
                }
            }
        }
        memset(f[i],0,sizeof(f[i]));
    }
    for (int j=0; j<=num; j++)
        ans=(ans+f[r%2][j][0][1]+f[r%2][j][1][1])%mod;
    printf("%d\n",ans);
    return 0;
}

一些练习题

[NOI2011]阿狸的打字机

我的题解

本文标题:AC自动机学习笔记

文章作者:Taduro

发布时间:2019年02月14日 - 14时51分

最后更新:2019年03月07日 - 14时30分

原始链接:http://dftyem.github.io/2019/02/14/AC自动机学习笔记/

许可协议: "署名-非商用-相同方式共享 3.0" 转载请保留原文链接及作者。

文章目录
  1. 1. AC自动机简介
  2. 2. 一些其他操作
    1. 2.1. fail树
    2. 2.2. AC自动机上DP
  3. 3. 一些练习题
,
载入天数...载入时分秒... 字数统计：75.7k