mydcwfy's Blog

AC 自动机

Posted on
Symbols count in article: 2.8k Reading time ≈ 6 mins.

字符串中相对比较难的知识点。

AC自动机

1. 前置知识

Trie & KMP.

KMP位置

但是，没看懂 KMP 不代表看不懂本博客。

2.解决的问题

多模问题，即一个字符串与多个模式串相匹配的问题。

如果不能匹配，找出最大的（模式串前缀）和（字符串的子串）相同。

3.核心思想

1）定义

在 Trie 上对每一个节点建立 $fail[i]$,是指的是对于所有模式串来说，当前所到节点的字符串的后缀与所有模式串的前缀的最大长度。

（ 令人难懂的定义）

对比 KMP，我们发现还是有一定的相似性的。

可以画一个 Trie，自行匹配。

2）求法

由于当前的 $fail$ 一定小于整个串的长度，所以我们跳到父节点。

然后模仿 KMP,一直向前 fail，直到当前的儿子节点与该节点所代表的相同。

我们搜索时，也和 KMP 相似，如果匹配失败，就一直 fail 直到可以。

举个例子。

首先，根的所有儿子的 $fail$ 都是指向根节点（没有可以和他匹配的了）。

对于其他节点 $u$，我们首先跳到父亲 $fa$。

以 $fa$ 为节点的字符串已经处理好了 $fail$，我们一直往上跳 $fail$，$fa$ 的后缀一定是包含当前节点。

再定义 $c$ 为 $u$ 是 $fa$ 的哪一个儿子。

如果碰到跳到的 $fail$ 有 $c$ 儿子，那么 $u$ 的 $fail$ 就指向 $c$ 儿子。

因为，$fa$ 的后缀与 $fail$ 的字符串一定相同。

所以，$u$ 的后缀一定与 $fail$ 的 $c$ 儿子相同。

3）一个小小的优化

Trie 图。

你可以先看后面的代码。

假设当前节点的儿子没有的话，我们可以直接指向 $fail[x]$ 的当前的儿子。

因为向下走的话，前面匹配的仍然匹配。

虽然一定程度上破坏了 Trie，但常数会小一些。

4.例题

T1：AC自动机

题目传送门 Luogu

题目传送门 AcWing

模板题。

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
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;

const int N=1e6+10,M=5e6+10;

int tr[N][26],ne[N],tot,cnt[N];
int q[N];
char str[M];

void insert()
{
    int u=0;
    for (int i=0;str[i];++i)
    {
        int t=str[i]-'a';
        if (!tr[u][t]) tr[u][t]=++tot;
        u=tr[u][t];
    }
    cnt[u]++;
}

void build()
{
    int hh=0,tt=-1;
    for (int i=0;i<26;++i)
        if (tr[0][i]) q[++tt]=tr[0][i];
    while (hh<=tt)
    {
        int x=q[hh++];
        for (int h=0;h<26;++h)
        {
            int &t=tr[x][h];
            if (!t) t=tr[ne[x]][h];
            else{
                ne[t]=tr[ne[x]][h];
                q[++tt]=t;
            }
        }
    }
}

int Calcans()
{
    int ans=0;
    for (int i=0,j=0;str[i];++i)
    {
        int t=str[i]-'a';
        j=tr[j][t];
        int p=j;
        while (p&&~cnt[p])
        {
            ans+=cnt[p];
            cnt[p]=-1;
            p=ne[p];
        }
    }
    return ans;
}

int main()
{
    int n;
    cin>>n;
    while (n--)
    {
        scanf("%s",str);
        insert();
    }
    build();
    scanf("%s",str);
    printf("%d\n",Calcans());
    return 0;
}

T2：[TJOI2013]单词

题目传送门 Luogu

题目传送门 AcWing

这道题略有不同，需要我们首先统计每一个节点属于那些字符串，然后使用 ne 的转移，就可以统计了。

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
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=1e6+10;
int tr[N][26],ne[N],cnt[N],id[250],tot,q[N],hh,tt=-1,n;
char str[N];

void insert(int x)
{
    int u=0;
    for (int i=0;str[i];i++)
    {
        int t=str[i]-'a';
        if (!tr[u][t]) tr[u][t]=++tot;
        u=tr[u][t];
        cnt[u]++;
    }
    id[x]=u;
    
}

void build()
{
    for (int i=0;i<26;++i)
        if (tr[0][i]) q[++tt]=tr[0][i];
    while (hh<=tt)
    {
        int x=q[hh++];
        for (int i=0;i<26;++i)
        {
            int &t=tr[x][i];
            if (!t) t=tr[ne[x]][i];
            else{
                ne[t]=tr[ne[x]][i];
                q[++tt]=t;
            }
        }
    }
}

int main()
{
    cin>>n;
    for (int i=1;i<=n;++i)
    {
        scanf("%s",str);
        insert(i);
    }
    build();
    for (int i=tt;i>=0;--i) cnt[ne[q[i]]]+=cnt[q[i]];
    for (int i=1;i<=n;++i) printf("%d\n",cnt[id[i]]);
    return 0;
}