AC自动机

OI 知识>字符串
1.6k words

AC 自动机

AC 自动机是以 Trie 树结构为基础，结合 KMP 思想建立的自动机，用于解决多模式匹配等任务。

一，概览

用两步建立一个 AC 自动机：

  1. 建立 Trie 树。（以 Trie 树为基础）
  2. 对 Trie 树上的所有结点构造失配指针。（结合 KMP 思想）

之后便可以用它进行匹配了。

二，字典树构建

AC 自动机所用的 Trie 就是普通的 Trie。

在 Trie 当中，结点表示某个模式串的前缀。Trie 的结点表示状态，边表示转移。

对于若干模式串 \(s_1,s_2,...,s_n\)，将它们构建成字典树后所有状态的集合记为 \(Q\)。

1
2
3
4
5
6
7
8
9
10
11
12
int cnt,tr[1000005][26],ended[1000005];
void insert(string s)
{
    int u=0;
    for(int i=0;s[i];i++)
    {
        if(!tr[u][s[i]-'a'])
            tr[u][s[i]-'a']=++cnt;
        u=tr[u][s[i]-'a'];
    }
    ended[u]++;
}

三，失配指针

AC 自动机利用 fail 指针辅助完成匹配。 理解 fail 指针对理解 AC 自动机意义重大。

1.理解 fail 指针

fail 指针从一个状态 \(u\) 出发，指向一个状态 \(v\)，Trie 树中每个状态对应一个由根结点出发的字符串，状态 \(v\) 所对应字符串是状态 \(u\) 所对应字符串的最长后缀。

有图为证：

fail的构建1.png

fail的构建2.png

fail 指针可以从 Trie 树上任意结点出发，其指向的结点可能为普通结点，也可能为模式串匹配结点，通过跳 fail 可以使同一位上匹配多个模式串，详细的运作规律将在下文讲解。

fail的构建3.png

实现 fail 指针

当前结点为 \(u\)，其父结点为 \(p\)，\(p\) 通过字符 \(c\) 指向 \(u\)，即 \(\delta(p,c)=u\)，若深度小于 \(u\) 的结点的 fail 指针均已知：

  1. 如果 \(\delta(\text{fail}[p],c)\) 存在，即状态 \(p\) 的最长后缀添加 \(c\) 后依然合法，而 \(u\) 是由状态 \(p\) 添加 \(c\) 得到的，此时状态 \(\delta(\text{fail}[p],c)\) 是 \(u\) 的最长后缀。
  2. 如果 \(\delta(\text{fail}[p],c)\) 不存在，则继续找 \(\text{fail}[p]\) 的 \(\text{fail}\) 指针，直到找到合法方案或跳至根结点。
  3. 若直到根结点也未找到合法方案，则 \(\text{fail}\) 指向根结点。

求fail1.png

求fail2.png

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int fail[1000005];
queue<int> q;
void build()
{
    for(int i=0;i<26;i++)
        if(tr[0][i]) q.push(tr[0][i]);
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        for(int i=0;i<26;i++)
        {
            if(tr[u][i])
            {
                fail[tr[u][i]]=tr[fail[u]][i];
                q.push(tr[u][i]);
            }
            else tr[u][i]=tr[fail[u]][i];
            //这里修改了 Trie 的结构
            //保证了失配时可以转移到一个合法的状态以便继续匹配
        }
    }
}

四，匹配的过程

匹配到每一位，不断跳 fail 并更新答案。

1
2
3
4
5
6
7
8
9
10
11
int query(string s)
{
    int u=0,ret=0;
    for(int i=0;i<s.size();i++)
    {
        u=tr[u][s[i]-'a'];
        for(int j=u;j&&ended[j]!=-1;j=fail[j])
            ret+=ended[j],ended[j]=-1;
    }
    return ret;
}

五，版

模板一

Luogu P3808【模板】AC 自动机（简单版） 

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
#include<bits/stdc++.h>
using namespace std;
int cnt;
int trie[1000005][26];
int fail[1000005],ended[1000005];
void insert(string s)
{
    int u=0;
    for(int i=0;i<s.size();i++)
    {
        if(!trie[u][s[i]-'a'])
            trie[u][s[i]-'a']=++cnt;
        u=trie[u][s[i]-'a'];
    }
    ended[u]++;
}
queue<int> q;
void build()
{
    for(int i=0;i<26;i++)
        if(trie[0][i]) q.push(trie[0][i]);
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        for(int i=0;i<26;i++)
        {
            if(trie[u][i])
            {
                fail[trie[u][i]]=trie[fail[u]][i];
                q.push(trie[u][i]);
            }
            else trie[u][i]=trie[fail[u]][i];
        }
    }
}
int query(string s)
{
    int u=0,ret=0;
    for(int i=0;i<s.size();i++)
    {
        u=trie[u][s[i]-'a'];
        for(int j=u;j&&ended[j]!=-1;j=fail[j])
            ret+=ended[j],ended[j]=-1;
    }
    return ret;
}
int n;
string s;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>s,insert(s);
    build();
    cin>>s;
    int ans=query(s);
    cout<<ans<<endl;
    return 0;
}

模板二

Luogu P3808【模板】AC 自动机（加强版） 

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
#include<bits/stdc++.h>
using namespace std;
int n;
string s[155],t;
int tot,tr[12005][26];
int fail[12005],id[12005],val[12005],cnt[12005];
void restart()
{
    memset(tr,0,sizeof(tr));
    memset(fail,0,sizeof(fail));
    memset(id,0,sizeof(id));
    memset(val,0,sizeof(val));
    memset(cnt,0,sizeof(cnt));
    tot=0;
}
void insert(string s,int m)
{
    int u=0;
    for(int i=0;i<s.size();i++)
    {
        if(!tr[u][s[i]-'a']) tr[u][s[i]-'a']=++tot;
        u=tr[u][s[i]-'a'];
    }
    id[u]=m;
}
queue<int> q;
void build()
{
    for(int i=0;i<26;i++)
    if(tr[0][i]) q.push(tr[0][i]);
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        for(int i=0;i<26;i++)
        {
            if(tr[u][i])
            {
                fail[tr[u][i]]=tr[fail[u]][i];
                q.push(tr[u][i]);
            }
            else tr[u][i]=tr[fail[u]][i];
        }
    }
}
void query(string t)
{
    int u=0,ret=0;
    for(int i=0;i<t.size();i++)
    {
        u=tr[u][t[i]-'a'];
        for(int j=u;j;j=fail[j]) val[j]++;
    }
    for(int i=0;i<=tot;i++)
        if(id[i])
        {
            ret=max(ret,val[i]);
            cnt[id[i]]=val[i];
        }
    cout<<ret<<endl;
    for(int i=1;i<=n;i++)
        if(cnt[i]==ret)
            cout<<s[i]<<endl;
    return;
}
int main()
{
    while(1)
    {
        cin>>n;
        if(n==0) break;
        restart();
        for(int i=1;i<=n;i++)
        {
            cin>>s[i];
            insert(s[i],i);
        }
        build();
        cin>>t;
        query(t);
    }
    return 0;
}

模板三

Luogu P3808【模板】AC 自动机（二次加强版） 

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
#include<bits/stdc++.h>
using namespace std;
map<char,int> H;
long long n;
string s;
long long tot,tr[2000005][26];
long long fail[2000005],val[2000005],id[200005];
void preH()
{
    for(char i='a';i<='z';i++)
        H[i]=(int)i-'a';
}
void insert(string s,long long m)
{
    long long u=0,siz=s.size();
    for(long long i=0;i<siz;i++)
    {
        if(!tr[u][H[s[i]]]) tr[u][H[s[i]]]=++tot;
        u=tr[u][H[s[i]]];
    }
    id[m]=u;
}
long long tmp1,tmp2;
long long q[2000005],indg[2000005];
void build()
{
    for(long long i=0;i<26;i++)
        if(tr[0][i]) q[++tmp2]=tr[0][i];
    while(tmp2-tmp1)
    {
        long long u=q[++tmp1];
        for(long long i=0;i<26;i++)
        {
            if(tr[u][i])
            {
                fail[tr[u][i]]=tr[fail[u]][i];
                indg[fail[tr[u][i]]]++;
                q[++tmp2]=tr[u][i];
            }
            else tr[u][i]=tr[fail[u]][i];
        }
    }
}
void topu()
{
    tmp1=tmp2=0;
    for(int i=1;i<=tot;i++)
        if(indg[i]==0) q[++tmp2]=i;
    while(tmp2-tmp1)
    {
        long long u=q[++tmp1],v=fail[u];
        indg[v]--,val[v]+=val[u];
        if(indg[v]==0) q[++tmp2]=v;
    }
}
void query(string t)
{
    long long u=0,siz=t.size();
    for(long long i=0;i<siz;i++)
        u=tr[u][H[t[i]]],val[u]++;
    topu();
    for(long long i=1;i<=n;i++)
        cout<<val[id[i]]<<endl;
    return;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    preH();
    cin>>n;
    for(long long i=1;i<=n;i++)
        cin>>s,insert(s,i);
    build();
    cin>>s;
    query(s);
    return 0;
}

\(Finished.\)

Comments