AC自动机详解

AC自动机详解

不是自动AC机

算法简介

啥是自动机?啥是AC自动机?

本蒟蒻对自动机并没有什么像样的理解,只知道AC自动机可以处理多个模式串在文本串中的匹配问题。

对于一般的匹配算法(KMP)只能一次处理单个模式串,而AC自动机可以做到快速的多模式串匹配。

前置技能:

算法讲解

建图

AC自动机是什么做到的?首先,他讲多个模式串建成一棵$Trie$,便于同时操作。

例如:模式串为sheheye

和KMP一样,如果我们已经匹配了串she,那么若当前失配(或匹配完成),我们便转向对hey的匹配,利用了已匹配的he

我们希望在e节点可以有一个“指针“指向”斜上方“的e节点(图中的红色箭头),失配时可跳到下一个节点,尽量多利用已匹配的长度。

这就是“$fail$指针”,(说是指针,用数组存就可以啦),记录$Trie$中每一个节点失配后的“去处”。

如何构造$fail$指针?当前子节点的fail指针指向父亲节点的$fail$节点(后者$fail$链上的节点)的对应子节点。

代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
std::queue<int> q;
fail[root]=root;
for(int i=0;i<26;++i)//对于Trie树前2层的节点特殊处理(显然他们的fail指向根)
if(ch[root][i])
{
fail[ch[root][i]]=root;
q.push(ch[root][i]);
}
while(!q.empty())
{
int k=q.front();q.pop();
for(int i=0;i<26;++i)//为当前节点k的子节点构建fail
if(ch[k][i])
{
int t=fail[k];
while(!ch[t][i]&&t)t=fail[t];
fail[ch[k][i]]=ch[t][i];
q.push(ch[k][i]);
}
}

查询

那么,我们如何查询答案呢?

我们发现,以每一个节点的$fail$节点($fail$指针指向的节点)结束的字符串是当前串的后缀。那么,从当前已匹配节点开始,一路走$fail$指针,如果遇到了某个模式串的结尾节点,那么该模式串就一点在当前串里出现。

所以我们只需将文本串在$Trie$中跑一遍(失配时跳向$fail$节点),对于每一个节点,沿$fail$指针的方向统计答案即可。

代码实现:

1
2
3
4
5
6
7
8
9
10
11
int k=root,ans=0;
for(int i=0;i<len;++i)
{
while(!ch[k][s[i]-'a']&&k)k=fail[k];//失配(匹配完成)时跳向fail节点
k=ch[k][s[i]-'a'];//因为root节点为0,所以不用考虑k为根的情况
if(end[k])//如果当前位置是某模式串的结束节点,统计答案
{
++ans;
end[k]=false;//避免重复统计(按照题意)
}
}

奇技淫巧:“路径压缩”

在构建$fail$指针的时候,若当前节点的某儿子节点不存在,便将儿子指针指向当前节点的$fail$节点的该儿子。

1
2
3
4
5
6
if(ch[k][i])
{
fail[ch[k][i]]=ch[fail[k]][i];
q.push(ch[k][i]);
}
else ch[k][i]=ch[fail[k]][i];

这样建好的$AC$自动机,在查询时不用考虑$fail$指针(因为提前放在儿子节点上了),只需跳向$fail$节点统计答案。

这时的$AC$自动机叫“$Trie$图”(说错了不要打我啊,我也不清楚啥是$Trie$图)。

1
2
3
4
5
6
7
8
9
10
11
int k=root,ans=0;
for(int i=0;i<len;++i)
{
k=ch[k][s[i]-'a'];
for(int t=k;t&&end[t]!=-1;t=fail[t])
if(end[t])
{
++ans;
end[t]=-1;//小优化,将已统计答案的结束节点置为-1
}
}

一般来说,这种优化后的$AC$自动机更加常用。

奇技淫巧:$fail$树

这是个啥玩意?我们发现,$fail$指针不可能成一个环,且最终都会指向根节点。

那么,我们将$fail$指针建成一棵以$Trie$的根节点为根的树,就会发现一些奇特的性质。

$x$节点的子树中的节点都是可以由$fail$跳向$x$的节点。

这就是说,当且仅当某字符串的所有节点在$x$节点的子树中,那么$x$字符串就会在该字符串中出现。

为了便于查询,我们可以通过**$dfs$序**对$fail$树进行维护,使用树状数组/线段树进行维护(甚至可以树剖)。

可实现**$log$查询(通常来说是求子树和,也就是树状数组区间求和)**,美滋滋。

例题:

  • [NOI2011]阿狸的打字机
  • [TJOI2013]单词