AC 自动机

2024-02-14 08:49:34

AC 自动机

学习 AC 自动机的第一要义：记住它不能帮你自动 AC ！！！

  • AC 自动机（以下简称 ACAM ），是一种多模式串匹配算法，它是由贝尔实验室的两位研究人员 Alfred V. Aho 和 Margaret J.Corasick 于1975年发明。

提到模式串匹配算法，你也许会想到大名鼎鼎的 KMP 算法。没错，它是最常用的单模式串匹配算法，但是如果要在一段文本串中一次性匹配 \(m\) 个模式串，KMP 就只能哈哈的跑 \(m\) 次，这个效率是我们无法接受的。为了解决“多模式串快速匹配”问题，人们发明了 ACAM。

Part 1 AC 自动机原理

在了解 ACAM 之前，你最好要了解以下前置知识：

  • KMP 模式串匹配（其实个人觉得不了解 KMP 也能学会 ACAM ）
  • Trie （熟练掌握）

学习 ACAM 怎么能没有图呢，让我们从图入手，构建一个 ACAM ！

假设你现在有 3 只模式串：bbaa,aa,abaa 。

第一步：构建 Trie 树

这一步很简单，就是把所有的模式串插入到一棵 Trie 里。构建出的 Trie 应该是这样的：（ Linux 画图还是挺费劲的，大家凑合凑合）

AC 自动机

插入的同时，可以在每个模式串的结尾打一个标记（红圈），表示这个模式串到结尾了。

Code

struct Trie{
  int fail,num;
  int ch[28];
}tr[maxn];

void Build(){
  int len=std::strlen(ch),u=0;
  for(int i=0;i<len;++i){
    int s=ch[i]-'a';
    if(tr[u].ch[s]==0) tr[u].ch[s]=++cnt;//没有就新建一个结点
    u=tr[u].ch[s];
  }
  tr[u].num++;//标记结尾结点
}

第二步：构建 fail 指针

这是 ACAM 的核心操作。

有些博客中说 fail 指针告诉我们如果当前结点失配了，该从哪里继续匹配，这固然是对的，但是不全面。

fail 指针的定义应该是：指向 可以与 以当前结点为结尾的 字符串的 某一个后缀 匹配的 最长的前缀的 末尾结点的 位置。

我知道这有点套娃，我们用图来理解会好一点，还是上面那个图：

AC 自动机

（为了方便区分，这里给结点编号 1 到 9 。我们用 xy 表示一个结点，x 表示这个结点的字符，y 表示这个结点的编号）

譬如这样，a3 是串 bba 的一个后缀，我们发现 a5 是某个串的一个前缀，而且和 bba 的后缀相同，而且最长。于是把 a3 的 fail 指向 a5 。

再来看 a4 ，显然 a4 的 fail 指针好像也可以指向 a5 。但是以 a4 为结尾的串 bbaa 有一个后缀是 aa ，而 a5,a6 正好构成了一个与之匹配的更长的前缀，于是 a4 的 fail 指针应该指向 a6 。

这样看起来比较无厘头，因为我们没有按照顺序求解 fail 指针，实际上，它是通过一发由根出发的 bfs 求出来的。

首先，规定根结点的儿子们的 fail 为根（因为它除了自己不可能有与它匹配的前缀），把根结点的儿子们入队。

每次取出队头 \(u\) ，扫描队头结点的所有非空的儿子 \(v\) ，\(v\) 的 fail 指针是 \(u\) 的 fail 指针指向结点的 \(v\) 儿子。

  • Q：为什么？

    A：显然，已经入队的结点的 fail 指针一定已经求好了，也就是我们找到了一个匹配的最长的前缀。现在 \(u\) 后面又来了一个字符 \(v\) ，那我们看看刚才匹配上的那个前缀存不存在一个结点 \(v'\) 与新来的 \(v\) 相同，如果有，我们就可以继续匹配这个前缀，就像例子中 3a,4a 的匹配那样。

  • Q：如果父节点 \(u\) 的 fail 指针没有与新来的 \(v\) 匹配的字符呢？

    A：这就需要我们保证它有一个这样的结点 \(v\) ，在下面会提到如何操作。

现在 \(u\) 还有一些空的儿子，我们在下一次求解 fail 的时候如果连向了这些空儿子，就相当于直接连向了根，不能保证“最长前缀”的性质，这样不好。所以我们需要保证 \(u\) 的每个儿子都非空。但是我们显然不可以无中生有给他造出来一个儿子，此时应该向别的结点“借”儿子。

假设现在有一个结点 \(w\) 要把它的 fail 边连向 \(u\) 的某个空儿子，那么分析一波性质：

  1. 根据定义，以 \(u\) 为结尾的前缀一定匹配以 \(w\) 的父亲为结尾的某个后缀。

  2. 考虑 \(u\) 的 fail 指针指向的结点 \(x\) ，以 \(x\) 结尾的前缀一定匹配以 \(u\) 为结尾的某个后缀。

那么可以推出：以 \(x\) 为结尾的前缀匹配以 \(w\) 的父亲为结尾的某个后缀。

大呼卧槽？没关系，看看下面的图，这有点像 KMP 跳 next 数组。

AC 自动机

假设以 \(u\) 为结尾的前缀，匹配了以 \(w\) 的父亲（记作 \(w'\) ）为结尾的某个后缀（红色部分为匹配上的字符），而以 \(x\) 为结尾的前缀又匹配了以 \(u\)​ 为结尾的某个后缀（蓝色部分为匹配上的字符），显然三段字符的蓝色部分都应该相等，也就是以 \(x\) 为结尾的前缀匹配以 \(w\) 的父亲为结尾的某个后缀。

总的来说，意思就是如果 \(w\) 要连接 fail 边的 \(v\) 在 \(u\) 的儿子中没有，应该到 \(x\) 中找 \(v\) 并连接 fail 边，因为以 \(x\) 为结尾的前缀匹配以 \(w'\) 为结尾的后缀。

但是写代码的时候，我们不可能每次都往上跳啊跳，直到找到一个有 \(v\) 儿子的结点吧，这样不仅麻烦，时间上也花费不起。所以为了方便，我们直接把 \(x\) 的 \(v\) 儿子 “借给” \(u\) ，也就是把 \(u\) 的 \(v\) 儿子连向 \(x\) 的 \(v\) 儿子。

  • Q：那如果 \(x\) 也没有 \(v\) 儿子呢？

    A：你怎么这么多屁话？ 我们处理 fail 基于 bfs，也就是说，在求 \(u\) 之前，一定已经求解完了 \(x\) 的 fail 指针。此时 \(x\) 的儿子该借的都借完了，不可能有空的。不过特别的，如果真的找不到结点借的话，就说明满足条件的结点不存在，我们也就不用考虑满足“最长”的性质了，直接把这个儿子连向根即可。

现在我们按照上面的方法，把上面图中的 fail 指针画出来吧：

AC 自动机

Code

void make_fail(){
  std::queue<int>q;
  for(int i=0;i<26;++i){
    if(tr[0].ch[i]!=0){
      tr[tr[0].ch[i]].fail=0;
      q.push(tr[0].ch[i]);
    }
  }//显然根节点的所有儿子的fail指针应该是0，把这些儿子入队
  while(q.size()){
    int u=q.front();//取出队头
    q.pop();
    for(int i=0;i<26;++i){
      int v=tr[u].ch[i];//枚举它的每个儿子
      if(v){//如果这个儿子非空
        tr[v].fail=tr[tr[u].fail].ch[i];
        //这个儿子的fail指针应该指向它父亲的fail指针指向的节点的这个儿子
        q.push(v);
      }else tr[u].ch[i]=tr[tr[u].fail].ch[i];
      //去fail指针指向的结点借儿子
    }
  }
}

第三步：匹配文本串

Mission：给你一个文本串，求出模式串中有几个出现在这个文本串中。

假设文本串是 bbaabaa 。

先拿出来刚才构建好的 Trie 图（由于我们有“借儿子”这种操作，它现在已经不是一棵树，而是一个 DAG 了话说自动机是不是都相当于构建了一个 DAG，雾）。

从根结点出发，开始匹配，每次在 Trie 图尝试往匹配文本串的方向跳，假设跳到了 \(u\) 。

从 \(u\) 出发，不停的跳 fail 边，直到跳到根，统计这期间跳到的模式串有哪些。

哈？为什么要跳 fail 边？因为以 fail 指针指向结点 \(w\) 为结尾的前缀是可以匹配以 \(u\) 为结尾的某个后缀的，而以 \(u\) 为结尾的后缀已经在文本串中出现了，也就相当于以 \(w\) 为结尾的前缀也在文本串中出现了，而这里面可能包含了一些模式串，如果不跳就会漏掉哦！

我们先跳前 4 个字符吧，蓝色是我们跳文本串的路径，而在跳到第四个字符的时候，我们沿着 fail 边跳的时候（红色），找到了一个模式串 aa 。

AC 自动机

接着匹配，发现 4a 好像没有儿子了，那怎么办，回根重新找？显然不对，如果回到根的话，你会发现 abaa 没被计入答案。

我们希望可以继续找到一个 b 字符以继续匹配。记得我们之前“借”的儿子吗？这时候他们又派上用场了，其实这里 4a 是有字符为 b 的儿子的，只是我们没画出来。在上面“借”儿子的过程中，6a 从 5a 借到了 7b 这个儿子，然后 4a 找到 6a 借，也借到了 7b 这个儿子，所以我们下一次应该去 7b 继续匹配。

由于上面我们已经把“借儿子”的过程处理好了，所以这里我们直接访问 4a 的字符为 b 的儿子就可以直接走到 7b 继续匹配了（没错就是啥也不干，躺平就完了）。

一直跳到文本串的结尾，匹配上了 9a ，于是 3 个模式串都出现在了文本串中，答案为 3 ，大功告成！如果细心的话你会发现，在 9a 跳 fail 边的时候又找到了一次模式串 aa 哦！（即为图中橙色边）

AC 自动机

既然我们只想知道文本串是不是出现过，就可以在跳 fail 边的时候打个标记，表示这个结点已经访问过了，这时跳出循环，节约了时间。

这种做法是基于 fail 边构成了一棵树的性质，我们称之为 fail 树。

  • Q：为什么 fail 是一棵树？

    A：每个结点有且仅有一条 fail 指针，又因为 Trie 树是联通的，所以这个东西满足“联通”与“有 n-1 条边”这两个性质，所以是树。

如果我们访问了树上的一条到根的链，那么我们就标记了这条链。下一次从别的结点开始跳的时候，可能会跳到这条链上，此时再要跳到根，实际上与之前跳过的路径是一样的。如果这一段重合路径中出现了模式串，那么在之前跳的时候一定已经被统计上了，所以这个做法是不会漏统计的。

Code

int AC_automaton(){
  int len=std::strlen(ch);
  int u=0,ans=0;
  for(int i=0;i<len;++i){
    int s=ch[i]-'a';//取出文本串的这一位
    u=tr[u].ch[s];//u跳到当前节点的这个儿子
    int v=u;
    while(v && tr[v].num!=-1){
      //不停跳fail指针直到跳到根，统计这一位匹配多少模式串
      ans+=tr[v].num;
      tr[v].num=-1;//标记已经访问过了
      v=tr[v].fail;
    }
  }
  return ans;//返回找到的模式串数量
}

时空复杂度

时间复杂度 \(O(N+\sum |s_i|)\) 其中 \(N\) 为文本串长度，\(\sum s_i\) 为模式串长度之和。

证明显然是我们扫描了文本串，在 fail 树上每个结点只会访问一次，实际上因为两个模式串存在公共前缀的原因，这个复杂度不可能跑满。

空间复杂度 \(O(N+\sum |s_i|)\) 这是记录下文本串和构建 Trie 的复杂度。（或许你可以一边读文本串一边跑 ACAM ，这样就是 \(O(\sum |s_i|)\) 的。。。

Part 2 总代码

其实上面给出的代码已经挺全面了，为了方便一些键盘上只有 Ctrl C V 的小伙伴，这里贴出总代码吧。

下面给出的参考代码以 洛谷P3808【模版】AC 自动机 为实现目标。

#include<bits/stdtr1c++.h>

namespace zhang_tao{
  #define inf 0x7f7f7f7f
  template <typename _T>
  inline _T const& read(_T &x){
    x=0;int fh=1;
    char ch=getchar();
    while(!isdigit(ch)){
      if(ch=='-')
        fh=-1;
      ch=getchar();
    }
    while(isdigit(ch)){
      x=x*10+ch-'0';
      ch=getchar();
    }
    return x*=fh;
  }
  void write(int x){
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+48);
  }
  inline int _gcd(const int x,const int y){
    return y?_gcd(y,x%y):x;
  }
  inline void _swap(int &x,int &y){
    x^=y^=x^=y;
  }
  #undef inf
} // namespace zhang_tao

using namespace zhang_tao;
const int maxn=1000005;

int n,cnt;
char ch[maxn];

struct Trie{
  int fail,num;
  int ch[28];
}tr[maxn];

void Build(){
  int len=std::strlen(ch),u=0;
  for(int i=0;i<len;++i){
    int s=ch[i]-'a';
    if(tr[u].ch[s]==0) tr[u].ch[s]=++cnt;
    u=tr[u].ch[s];
  }
  tr[u].num++;
}

void make_fail(){
  std::queue<int>q;
  for(int i=0;i<26;++i){
    if(tr[0].ch[i]!=0){
      tr[tr[0].ch[i]].fail=0;
      q.push(tr[0].ch[i]);
    }
  }//显然根节点的所有儿子的fail指针应该是0，把这些儿子入队
  while(q.size()){
    int u=q.front();//取出队头
    q.pop();
    for(int i=0;i<26;++i){
      int v=tr[u].ch[i];//枚举它的每个儿子
      if(v){//如果这个儿子不是0
        tr[v].fail=tr[tr[u].fail].ch[i];
        //这个儿子的fail指针应该指向它父亲的fail指针指向的节点的这个儿子
        q.push(v);
      }else tr[u].ch[i]=tr[tr[u].fail].ch[i];
      //这个节点直接失配了，去u的fail指针继续尝试匹配
    }
  }
}

int AC_automaton(){
  int len=std::strlen(ch);
  int u=0,ans=0;
  for(int i=0;i<len;++i){
    int s=ch[i]-'a';//取出文本串的这一位
    u=tr[u].ch[s];//u跳到当前节点的这个儿子
    int v=u;
    while(v && tr[v].num!=-1){
      //不停跳fail指针直到跳到0，统计这一位匹配多少模式串
      ans+=tr[v].num;
      tr[v].num=-1;
      v=tr[v].fail;
    }
  }
  return ans;
}

signed main(){
  read(n);
  for(int i=1;i<=n;++i){
    scanf("%s",ch);
    Build();
  }
  tr[0].fail=0;
  make_fail();
  scanf("%s",ch);
  write(AC_automaton()),putchar('\n');
  return 0;
}

结语

关于 ACAM 的基础知识的分享就到这里了，如果您觉得不明白的话，可以参考上面的图文，进行手动画图推导，亲测这样十分有助于理解。

如果您觉得我讲的不错的话，可以点个赞吗？/kel

如果您有疑问的话，欢迎评论或者加笔者邮箱（在侧边栏里）。

PS：如果你只会 ACAM 模版的话，那你也就只能做 ACAM 模版题了。

关于 ACAM 的一些做题技巧，我会再写一篇博客，分享给大家。

上一篇：2021牛客暑期多校训练营第一场


下一篇：快乐的一天从AC开始 | 20210714 | P3594