AC自动机

发表于 更新于

前言

KMP是一种很神奇的算法，它能够快速匹配模式串与文本串。但是如果遇到了多个模式串的情况，KMP 就需要 $O(k\times(n+m))$ 的时间，在 $k$ 很大的时候，KMP 是过不了这个题的，所以我们就需要一个新的算法：AC自动机。

AC自动机

模板题：P3808 【模板】AC 自动机（简单版）
我们已经知道了 Trie 和 KMP，一个是用于储存多个字符串，另一个是在一个文本串中查找一个模式串。而 AC 自动机需要实现在一个文本串中查找多个模式串，所以我们只需要将上面两者结合即可。
在 KMP 中，每一个节点都有一个失配指针，在文本串与模式串失配后跳转到模式串的对应位置。如果我们把 Trie 上的每一个节点都配上一个失配指针，只要文本串与字典树在此失配后跳转到字典树对应节点即可。失配指针指向的节点对应的字符串一定是适配节点对应的字符串的后缀，这样这个节点才能与文本串匹配。
但是字典树上不只有一个模式串，在一个位置可能有多个模式串可以匹配上文本串。但是在这个字符串已经与文本串匹配的时候，下一个可以匹配的字符串一定也可以和这个字符串匹配，所以下一个字符串一定是这一个字符串的后缀。刚好，失配指针也是要找到对应字符串的后缀，所以我们在找更多可以匹配的模式串时只需要跳转到失配指针对应的节点即可，虽然并没有失配。
AC 自动机的实现大概分为以下三步：建字典树、求失配指针指针、跑 AC 自动机。
字典树的建立和平常没有什么区别，只是要注意不仅要存每个节点是否有结束的模式串，还要记录有多少个。

1
2
3
4
5
6
7
8
9
10
11
void build(char *x)
{
    int k=1;    //表示当前节点
    for(int i=1;x[i];++i)   //依次匹配模式串的每个字符
    {
        if(a[k][x[i]-'a']==0) a[k][x[i]-'a']=++q;
        //如果没有当前字符对应的节点，就新建一个节点。
        k=a[k][x[i]-'a'];//跳转到下一个节点
    }
    ++g[k]; //记录当前节点的模式串个数
}

求失配指针相当于是 AC 自动机的核心，也是最难理解的地方。
在建好字典树后，我们一般用 bfs 遍历整棵树。注意在遍历过程中数组f储存的是已配指针。同样，失配指针是储存在数组f中的。在求一个点的失配指针时，共有2种情况。
不过在求失配指针时，我们还会用到一些不存在的节点。这些点存在的意义就是让程序在匹配时知道如果文本串对应到这个点就会失配，并直接给出失配指针，这样可以更加的方便。
在开始前，我们还要将 $0$ 号节点的所有儿子设为根节点，因为如果有一个点对应的字符串无法在字典树中找到它的后缀，它的失配指针就会指向 $0$ 的儿子 $x$，但是实际上它应该跳转到根节点，所以把0号点所有儿子都指向根节点即可。
当我们搜索到点 $i$，它对应的字符为 $x$，父节点为 $k$。当点i存在时，它的失配指针就是点k的失配指针指向的节点的儿子 $x$。什么意思，见下图：
![1](https://cdn.luogu.com.cn/upload/image_hosting/udw2lc47.png?x-oss-process=image/resize,m_lfit,h_170,w_225 =300x200)
![2](https://cdn.luogu.com.cn/upload/image_hosting/jae281vb.png?x-oss-process=image/resize,m_lfit,h_170,w_225 =300x200)
（图片来自网络）
第一幅图就是第一步建立出来的字典树，第二幅图表示每个节点的失配指针。举个例子，我们现在在访问最左侧的节点 $c$，它的父节点是上面的点 $b$，点 $b$ 的失配指针指向根节点的儿子 $b$。点 $c$ 对应的字符串是 $abc$。我们先找到 $b$ 的失配节点，也就是中间的 $b$，然后再找到 $b$ 位置对应的儿子 $c$，也就是中间的点 $c$，这样我们就找到了它对应的失配指针。
如果点 $k$ 的失配指针指向的节点没有儿子节点 $x$ 怎么办？其实是一样的，由于这个点不存在，所以这个位置就不存在原字符串的后缀，它的失配指针其实就直接指向了这个点的失配指针，所以它总会指向一个存在的点。在求完失配指针后，我们还要讲这个点入队来继续 bfs。
当我们搜索到点 $i$，它对应的字符为 $x$，父节点为 $k$。当点 $i$ 不存在时，点 $k$ 的儿子 $x$ 就是点 $k$ 的失配指针指向的节点的儿子 $x$。
因为点 $i$ 不存在，所以文本串如果匹配到此处必然失配，所以我们可以简单地将点 $k$ 的儿子 $x$ 指向点i的失配节点。点 $i$ 的失配指针的求法同上，就是点k的失配节点的儿子 $x$ 。由于这个点实际上不存在，所以不需要入队。如图：
![3](https://cdn.luogu.com.cn/upload/image_hosting/z4n1xw48.png?x-oss-process=image/resize,m_lfit,h_170,w_225 =300x200)

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
void bfs()
{
    queue<int> Q;   //搜索时用的队列
    for(int i=0;i<=25;++i)  //将节点0的所有儿子设为1
    {
        a[0][i]=1;
    }
    f[1]=0; //根节点的失配指针只用于求其它点的失配指针
    Q.push(1);  //根节点入队
    while(!Q.empty())   //bfs
    {
        int k=Q.front();    //提取队首节点
        Q.pop();
        for(int i=0;i<=25;++i)  //访问所有儿子节点
        {
            if(a[k][i]!=0)  //这个点存在
            {
                Q.push(a[k][i]);    //入队
                f[a[k][i]]=a[f[k]][i];  //求失配指针
            }
            else    //这个点不存在
            {
                a[k][i]=a[f[k]][i]; //求失配指针
            }
        }
    }
}

在求完失配指针后，我们就可以跑 AC 自动机了。
首先我们需要定义一个变量 $x$ 记录当前匹配到的字典树节点，初始值为 $1$，还有一个变量s储存出现过的模式串个数。
然后我们要依次访问整个文本串。每一次访问都将x更新为节点x对应文本串当前字符的儿子。如果节点 $x$ 有这个儿子，那么x就会指向这一个儿子节点；如果没有，它就会自动跳转到节点 $x$ 的失配指针指向的节点。然后我们要新定义一个变量 $k = x$，循环访问节点 $k$ 的失配指针指向的节点，找到的这些都是可以与文本串匹配的字符串，所以我们要在这时记录个数，不过还要用一个数组来判断一个模式串是否已经被记录过。如果某一次节点 $k$ 已经被记录过，那么之前一定也记录过点 $k$ 之后所有可以与文本串匹配的模式串，所以可以直接退出循环。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
char c[1000001];
cin>>c+1;
int m=strlen(c+1);
int s=0,x=1;
for(int i=1;i<=m;++i)   //依次访问文本串
{
    x=a[x][c[i]-'a'];   //更新当前的点
    int k=x;
    while(k!=0&&h[k]==false)//记录所有可以匹配的模式串
    {
        s+=g[k];    //计数
        h[k]=true;  //标记
        k=f[k];     //跳转至下一个
    }
}

AC自动机加强版

模板题：【模板】AC 自动机（加强版）
模板题：【模板】AC 自动机（二次加强版）
有的时候我们不仅要求出一个模式串是否在文本串中出现过，我们还需要知道它出现的次数。这时候我们就需要修改一下之前的方法，我们不能跳过已经有标记的点了，就像这样：

1
2
3
4
5
while(k!=0)
{
    h[k]+=g[k];
    k=f[k];
}

这样下来一个点就可能不止被访问一遍，于是就会导致 $\color{purple}{TLE}$。如何解决这个问题呢？如果我们把一个点的失配指针指向的点和这个点连接起来，那么就会形成一个链，如果位于链首的点匹配成功一次，意味着后面所有点都会匹配成功一次。所以我们可以先统计第一个点匹配的次数，最后再更新后面所有点，复杂度就可以大大降低了。如何实现？我们再把失配指针当做一条有向边，所有的点必然会形成一个有向无环图，所以只需要在最后进行拓扑排序即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void abc()
{
    queue<int> Q;       //定义队列
    for(int i=1;i<=q;++i)
    {
        if(r[i]==0) Q.push(i);      //入度为0的点入队
    }
    while(!Q.empty())
    {
        int k=Q.front();
        Q.pop();
        h[f[k]]+=h[k];      //统计
        --r[f[k]];      //入度减一
        if(r[f[k]]==0) Q.push(f[k]);    //如果入度为0则入队
    }
}

code

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
#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
using namespace std;
int n,q=1,a[1000001][26],f[1000001],g[1000001],h[1000001],r[1000001];
void build(char *x,int t)
{
    int k=1;
    for(int i=1;x[i];++i)
    {
        if(a[k][x[i]-'a']==0)
        {
            a[k][x[i]-'a']=++q;
        }
        k=a[k][x[i]-'a'];
    }
    g[t]=k;
}
void bfs()
{
    queue<int> Q;
    for(int i=0;i<=25;++i)
    {
        a[0][i]=1;
    }
    f[1]=0;
    Q.push(1);
    while(!Q.empty())
    {
        int k=Q.front();
        Q.pop();
        for(int i=0;i<=25;++i)
        {
            if(a[k][i]!=0)
            {
                Q.push(a[k][i]);
                f[a[k][i]]=a[f[k]][i];
                ++r[a[f[k]][i]];
            }
            else
            {
                a[k][i]=a[f[k]][i];
            }
        }
    }
}
void abc()
{
    queue<int> Q;
    for(int i=1;i<=q;++i)
    {
        if(r[i]==0) Q.push(i);
    }
    while(!Q.empty())
    {
        int k=Q.front();
        Q.pop();
        h[f[k]]+=h[k];
        --r[f[k]];
        if(r[f[k]]==0) Q.push(f[k]);
    }
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
    {
        char x[200001];
        cin>>x+1;
        build(x,i);
    }
    bfs();
    char c[2000001];
    cin>>c+1;
    int m=strlen(c+1);
    int x=1;
    for(int i=1;i<=m;++i)
    {
        x=a[x][c[i]-'a'];
        ++h[x];
    }
    abc();
    for(int i=1;i<=n;++i)
    {
        printf("%d\n",h[g[i]]);
    }
    return 0;
}