AC 自动机查漏补缺
前言
今年 1 月份学过一次，当时自以为掌握得很好，实际上就是依托答辩。而且还有很多地方是有严重误导性的。所以这篇查漏补缺就是记录一下自己对 AC 自动机尚不完全掌握的地方。并对之前的那篇不太正确的题解进行纠正。
因此，在这样的背景下，这篇文章注定就不是给初学者看的，是大致了解了 AC 自动机是什么后的一篇提高读物。
当然你硬要初学就来看也没问题，毕竟此篇文章与重头开始写没有什么区别。
三问 AC 自动机
第一问：AC 自动机到底是什么？
KMP 是解决单模式串匹配问题的算法，而 AC 自动机则可以解决多模式串匹配问题。
第二问：AC 自动机靠什么实现？
通过多模式串建起一棵 Trie 树，再构建 Trie 上每个点的失配指针（fail），由此可得 Fail 树。将文本串在 Trie 上留痕。然后就可以得到文本串前缀的信息。根据 Fail 树的定义可以更新这些前缀的后缀，即文本串的子串。同时如果该子串如果是模式串则可以维护模式串的信息了。
第三问：AC 自动机为什么叫“自动机”？
自动机是一种数学模型，至于它的深层的定义可以去看《自动机 - OI Wiki》。
三问 Fail 树
第一问：Fail 树是怎么冒出来的？
AC 自动机一个重要的步骤是构建失配指针，即 fail 指针。某个点的 fail 指针所指向的点在 Trie 上对应的字符串是该点在 Trie 上对应的字符串的最大后缀（“对应的字符串”指 Trie 上的根节点到此点的路径上的字符构成的串）。所以每个点都只有一个 fail 指针（可能指向根节点），每个点也有可能被多个节点的失配指针指向。这个就很像父子关系，所以 fail 指针构造出来后，即得到了一棵 Fail 树。
第二问：Fail 树和 Trie 树有什么区别？
Fail 树上每个节点的祖先都是该点在 Trie 上对应字符串的后缀。Trie 树是把每个模式串塞进去而建起来的。当文本串在 Trie 上留痕后，一个留痕过的点从根节点到它的路径上形成的字符串就是文本串的前缀（这个很显然啦~）。
第三问：Fail 树和 Trie 树有什么联系？
首先是在 Trie 上将文本串留痕，边留痕边在该节点记录信息。这样结束后便得到了文本串前缀的信息。我们还想处理文本串子串的信息。这时候需要搬出我们的 Fail 树。拓扑排序，从叶子节点将信息传递到父亲节点。为什么呢？因为 Fail 树上的祖先是该点的后缀，而前缀的后缀就是子串。为什么可以这样？因为该点是文本串留痕过的点，说明此时是可以匹配上文本串的。既然该点的串可以匹配上，那该点的串的后缀必然也是可以匹配上的。
典型例题
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<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6+5,M=30;
int n;
char str[N],s[N];
int tr[N][M],fail[N],tot,deg[N],pos[N];
bool vis[N];
void ins(char *s,int j)
{
int len=strlen(s),root=0;
for(int i=0;i<len;i++)
{
if(!tr[root][s[i]-'a'])
tr[root][s[i]-'a']=++tot;
root=tr[root][s[i]-'a'];
}
pos[j]=root;
}
void FL()
{
queue<int> q;
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 AC()
{
int len=strlen(str),root=0;
for(int i=0;i<len;i++)
{
root=tr[root][str[i]-'a'];
vis[root]=1;
}
for(int i=1;i<=tot;i++)
deg[fail[i]]++;
queue<int> q;
for(int i=1;i<=tot;i++)
if(!deg[i])
q.push(i);
while(!q.empty())
{
int u=q.front();q.pop();
if(!u) continue;
vis[fail[u]]=1;
deg[fail[u]]--;
if(!deg[fail[u]])
q.push(fail[u]);
}
}
signed main()
{
scanf("%lld",&n);
for(int i=1;i<=n;i++)
{
scanf("%s",s);
ins(s,i);
}
scanf("%s",str);
FL();
AC();
int ans=0;
for(int i=1;i<=n;i++)
if(vis[pos[i]])
++ans;
printf("%lld\n",ans);
return 0;
}
|
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
|
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6+5,M=30,L=80;
int n;
char str[N],s[N][L];
int tr[20000][M],fail[N],tot,pos[N];
int vis[N];
void ins(char *s,int j)
{
int len=strlen(s),root=0;
for(int i=0;i<len;i++)
{
if(!tr[root][s[i]-'a'])
tr[root][s[i]-'a']=++tot;
root=tr[root][s[i]-'a'];
}
pos[tot]=j;
}
void FL()
{
queue<int> q;
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 AC()
{
int len=strlen(str),root=0;
for(int i=1;i<=tot;i++)
vis[i]=0;
for(int i=0;i<len;i++)
{
root=tr[root][str[i]-'a'];
for(int j=root;j;j=fail[j])
vis[pos[j]]++;
}
}
signed main()
{
while(~scanf("%lld",&n)&&n)
{
memset(fail,0,sizeof(fail));
memset(tr,0,sizeof(tr));
memset(pos,0,sizeof(pos));
tot=0;
for(int i=1;i<=n;i++)
{
scanf("%s",s[i]);
ins(s[i],i);
}
// cerr<<tot<<"\n";
scanf("%s",str);
FL();
AC();
int ans=0;
for(int i=1;i<=n;i++)
ans=max(ans,vis[i]);
printf("%lld\n",ans);
for(int i=1;i<=n;i++)
if(vis[i]==ans)
puts(s[i]);
}
return 0;
}
|
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
|
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+5,M=30,L=80;
int n;
char str[N*10],s[N][L];
int tr[N][M],fail[N],tot,deg[N],pos[N];
int vis[N];
void ins(char *s,int j)
{
int len=strlen(s),root=0;
for(int i=0;i<len;i++)
{
if(!tr[root][s[i]-'a'])
tr[root][s[i]-'a']=++tot;
root=tr[root][s[i]-'a'];
}
pos[j]=root;
}
void FL()
{
queue<int> q;
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 AC()
{
int len=strlen(str),root=0;
for(int i=0;i<len;i++)
{
root=tr[root][str[i]-'a'];
vis[root]++;
}
queue<int> q;
for(int i=1;i<=tot;i++)
deg[fail[i]]++;
for(int i=1;i<=tot;i++)
if(!deg[i])
q.push(i);
while(!q.empty())
{
int u=q.front();q.pop();
if(!u) continue;
vis[fail[u]]+=vis[u];
deg[fail[u]]--;
if(!deg[fail[u]])
q.push(fail[u]);
}
}
signed main()
{
scanf("%lld",&n);
for(int i=1;i<=n;i++)
{
scanf("%s",s[i]);
ins(s[i],i);
}
scanf("%s",str);
FL();
AC();
int ans=0;
for(int i=1;i<=n;i++)
printf("%lld\n",vis[pos[i]]);
return 0;
}
|
后记
感觉例题没什么好说的，这篇文章本来就不是详解，只是一点查漏补缺。代码都是在写文章当天重写过一遍的，以此来加深印象。
另：之前那篇《浅谈 AC 自动机》有些有错误的地方，例如 fail 指针的构建根本就不是路径压缩，而是记忆化。