AC 自动机·Automaton

摘要

之前洛谷日报上发了一篇《强势图解 AC 自动机》,现在复习一下,重新整理思路

概述

AC 自动机是一种有限状态自动机(说了等于没说),它常被用于多模式串的字符串匹配。

AC 自动机是以 TRIE 的结构为基础,结合KMP 的思想建立的。

建立一个 AC 自动机通常需要两个步骤:

  • 基础的 TRIE 结构:将所有的模式串构成一棵
  • KMP 的思想:对 树上所有的结点构造失配指针。

然后就可以利用它进行多模式匹配了。

声明:代码部分的字符串都以1为起点

TRIE 构建

的 insert 操作一模一样(强调!一模一样!)

因为我们只利用 TRIE 的结构,所以直接将模式串存入即可。

失配指针

在讲构造以前,先来对比一下这里的 指针与 KMP 中的 next 指针:

共同点:两者同样是在失配的时候用于跳转的指针。

不同点: 指针求的是最长 ,而 指针指向所有模式串的前缀中匹配当前状态的最长后缀。

因为 KMP 只对一个模式串做匹配,而 AC 自动机要对多个模式串做匹配。有可能 指针指向的结点对应着另一个模式串,两者前缀不同。

也就是说,AC 自动机在对匹配串做逐位匹配时,同一位上可能匹配多个模式串。因此 指针会在字典树上的结点来回穿梭,而不像 KMP 在线性结构上跳转。

构建指针

下面介绍构建 指针的基础思想:(强调!基础思想!基础!)

构建 指针,可以参考 KMP 中构造 指针的思想。

考虑字典树中当前的节点 的父节点是 通过字符 的边指向 ,即 。假设深度小于 的所有节点的 指针都已求得。

我们跳转到

  • 如果 存在:则让 指针指向 。相当于在 后面加一个字符 ,就构成了
  • 如果 不存在:那么我们继续找到 ,重复上述判断过程,一直跳 指针直到根节点。
  • 如果真的没有,就让 指针指向根节点。

如此即完成了 的构建。

例子

下面放一张 GIF 帮助大家理解:

对字典树{i,he,his,she,hers}构建 指针:

  • 黄色结点表示当前的结点 ,绿色结点表示已经 BFS 遍历完毕的结点,红 / 橙色的边表示 指针。
  • 2 号节点的 指针画错了,$fail2=0$.
    AC_automation_gif_b_3.gif
  • 我们重点分析结点 6 的 指针构建:
    AC_automation_6_9.png
  • 找到 6 的父节点 5,5 的 指针指向 10,然而 10 结点没有字母’s’连出的边;
  • 所以跳到 10 的 指针指向的结点 0,发现 0 结点有字母’s’连出的边,指向 7 结点;
  • 所以 $fail6=7$.

另外,在构建 指针的同时,我们也对 中模式串的结尾构建 指针。这样在匹配到结尾后能自动跳转到下一个匹配项。具体见代码实现。

字典树与字典图

关于insert()笔者不做分析,先来看build():

void build(){
for(int i=0;i<26;i++)if(tr[0][i])q.push(tr[0][i]);
while(q.size()){
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];
}
}
}

build函数将结点按BFS顺序入队,依次求fail指针。

这里的字典树根节点为 0,我们将根节点的子节点一一入队。

若将根节点入队,则在第一次 BFS 的时候,会将根节点的子节点的 指针标记为本身。

而将根节点的子节点入队,也不影响算法正确性(因为 指针初始化为 0)

然后开始 BFS:

每次取出队首的结点 u。 指针已经求得,我们要求 u 的子节点们的 指针。然后遍历字符集(这里是 0-25,对应 a-z):

  • 如果 存在,我们就将这个子节点的 指针赋值为 的字符 i 对应的结点。Q2- 不是应该用 while 循环,不停的跳 指针,判断是否存在字符 i 对应的结点,然后赋值吗?怎么一句话就完了?
  • 否则, 不存在,就将 的字符 i 对应的子节点编号赋值给 .Q3- 等等,说好的字典树呢?怎么将 的子节点直接赋成 的子节点去了?

Q2&Q3

Q2 与 Q3 的代码是相辅相成的。

简单地来讲,我们将 指针跳转的路径做了压缩(就像并查集的路径压缩),使得本来需要跳很多次 指针变成跳一次。

而这个路径压缩的就是 Q3 的代码在做的事情之一

我们将之前的 GIF 图改一下:
AC_automation_gif_b_pro3.gif

蓝色结点表示 BFS 遍历到的结点 u,深蓝色、黑色的边表示执行完 Q3 代码连出的字典树的边。

可以发现,众多交错的黑色边将字典树变成了字典图。图中省略了连向根节点的黑边(否则会更乱)。

我们重点分析一下结点 5 遍历时的情况,这时我们求 指针:
AC_automation_b_7.png

本来应该跳 次才能找到 号结点,但是我们通过 号结点的黑色边直接通过字母 找到了 7 号结点。

因此,Q2 结合了 Q3 的代码,就能在 的时间内对单个结点构造 指针。

这就是 build 完成的两件事:构建 指针和建立字典图。这个字典图也会在查询的时候起到关键作用。

多模式匹配

接下来分析匹配函数query():

int query(char *t){
int u=0,res=0;
for(int i=1;t[i];i++){
u=tr[u][t[i]-'a'];//转移
for(int j=u;j&&e[j]!=-1;j=fail[j]){
res+=e[j],e[j]=-1;
}
}
return res;
}

声明 作为字典树上当前匹配到的结点,res 即返回的答案

循环遍历匹配串,p 在字典树上跟踪当前字符。

利用 指针找出所有匹配的模式串,累加到答案中。然后清 0。

取反的操作用来判断 是否等于 -1。

Q- 读者可能纳闷了:你这里的 一直在往字典树后面走,没有跳 指针啊!这和 KMP 的思想不一样啊,怎么匹配得出来啊

Answer to Q

还记得刚才的字典图吗?事实上你并不是一直在往后跳,而是在图上穿梭跳动。比如,刚才的字典图:
AC_automation_b_13.png

我们从根节点开始尝试匹配ushersheishis,那么 的变化将是:
AC_automation_gif_c.gif

红色结点表示 结点,粉色箭头表示 在字典图上的跳转,浅蓝色的边表示成功匹配的模式串,深蓝色的结点表示跳 指针时的结点。

其中的部分跳转,我们利用的就是新构建的字典图上的边,它也满足后缀相同(sher 和 her),所以自动跳转到下一个位置。

综上, 指针的意义是,在匹配串同一个位置失配时的跳转指针,这样就利用 指针在同一位置上进行多模式匹配,匹配完了,就在字典图上自动跳转到下一位置。

总结

到此,你已经理解了整个 AC 自动机的内容。我们一句话总结 AC 自动机的运行原理:

构建字典图实现自动跳转,构建失配指针实现多模式匹配。

模板

LuoguP3808【模板】AC自动机(简单版)

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+6;
int n;

namespace AC{
int tr[N][26],tot;
int e[N],fail[N];
void insert(char *s){
int u=0;
for(int i=1;s[i];i++){
if(!tr[u][s[i]-'a'])tr[u][s[i]-'a']=++tot;
u=tr[u][s[i]-'a'];
}
e[u]++;
}
queue<int> q;
void build(){
for(int i=0;i<26;i++)if(tr[0][i])q.push(tr[0][i]);
while(q.size()){
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];
}
}
}
int query(char *t){
int u=0,res=0;
for(int i=1;t[i];i++){
u=tr[u][t[i]-'a'];//转移
for(int j=u;j&&e[j]!=-1;j=fail[j]){
res+=e[j],e[j]=-1;
}
}
return res;
}
}

char s[N];
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%s",s+1),AC::insert(s);
scanf("%s",s+1);
AC::build();
printf("%d",AC::query(s));
return 0;
}

模板2

P3796 【模板】AC自动机(加强版)

#include<bits/stdc++.h>
using namespace std;
const int N=156,L=1e6+6;
namespace AC{
const int SZ=N*80;
int tot,tr[SZ][26];
int fail[SZ],idx[SZ],val[SZ];
int cnt[N];//记录第i个字符串的出现次数
void init(){
memset(fail,0,sizeof(fail));
memset(tr,0,sizeof(tr));
memset(val,0,sizeof(val));
memset(cnt,0,sizeof(cnt));
memset(idx,0,sizeof(idx));
tot=0;
}
void insert(char *s,int id){//id表示原始字符串的编号
int u=0;
for(int i=1;s[i];i++){
if(!tr[u][s[i]-'a'])tr[u][s[i]-'a']=++tot;
u=tr[u][s[i]-'a'];
}
idx[u]=id;
}
queue<int> q;
void build(){
for(int i=0;i<26;i++)if(tr[0][i])q.push(tr[0][i]);
while(q.size()){
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];
}
}
}
int query(char *t){//返回最大的出现次数
int u=0,res=0;
for(int i=1;t[i];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(idx[i])res=max(res,val[i]),cnt[idx[i]]=val[i];
return res;
}
}
int n;
char s[N][100],t[L];
int main(){
while(~scanf("%d",&n)){
if(n==0)break;
AC::init();
for(int i=1;i<=n;i++)scanf("%s",s[i]+1),AC::insert(s[i],i);
AC::build();
scanf("%s",t+1);
int x=AC::query(t);
printf("%d\n",x);
for(int i=1;i<=n;i++)if(AC::cnt[i]==x)printf("%s\n",s[i]+1);
}
return 0;
}
/*
* BUG#1 build的时候忘了push(tr[u][i])
* BUG#2 误以为倒序遍历AC自动机就是BFS的倒序,实际上不是这样
*/