【算法】AC自动机

请注意,本文编写于 256 天前,最后修改于 86 天前,其中某些信息可能已经过时。

AC自动机 不是 自动AC机
AC自动机 不是 自动AC机
AC自动机 不是 自动AC机

自动机是计算理论的一个概念,其实是一张“图”,每个点是一个“状态”,而边则是状态之间的转移,根据条件能指导从一个状态走向另一个状态

AC自动机(Aho-Corasick automation),是一种多模匹配算法
比较常见的例子时给出 $n$ 个单词,再给出 $m$ 个字符的文章,找出有多少个单词在文章中出现过

知识储备

KMP
Trie

原理

首先, KMP 匹配算法每次能够匹配一个单词和一个文本串
Trie 则能将多个单词组合起来,形成一个树形结构

所以对于要匹配的单词,我们先将其用 Trie 组合起来

void insert(char *s) {
    int now = 0 , n = strlen(s);
    for(int i = 0 ; i < n ; ++ i) {
        int c = s[i] - 'a';
        if(!ch[now][c]) ch[now][c] = ++ cnt;
        now = ch[now][c];
    }
    ++ val[now];//这里指以 now 这个节点结尾的字符串个数
}

然后在 Trie 树上求失配指针 $fail$ ,这也是 AC自动机 的精髓所在
什么是 $fail$ 指针?
就是当前点匹配成功而匹配下一点失败需要转移到的位置
这个位置应该是当前串的最长后缀

构建方法:

  • 利用BFS的方法来遍历整棵 Trie ,保证所有比当前节点深度小的节点都已经处理完毕了
  • 假设现在已经处理到节点 $x$ , x 的 $fail$ 指针已经确定

    • 若 $x$ 有儿子 $c$ 那么将 $fail[c]$ 设为 $ch[fail[x]][c]$
    • 若 $x$ 没有儿子 $c$ 那么直接将 $ch[x][c]$ 设为 $ch[fail[x]][c]$

      • 考虑一下这个算法的正确性
      • 如果当前节点没有儿子 $c$ ,将状态直接转移到有儿子 $c$ 的最长后缀是没有问题的
      • 所以 $fail[x]$ 是不可能没有儿子 $c$ 的,因为 $fail[x]$ 比 $x$ 要短,那么它的所有儿子肯定已经处理,如果本来没有也肯定从某个具有儿子 $c$ 的最长后缀转移过来了,最多是从 $rt$ 转移过来而恰好 $rt$ 也没有这个儿子导致这个儿子为 $0$
      • 如果当前节点有儿子 $c$ ,那么其最长后缀 $fail[ch[x][c]]$ 应该由 $fail[x]$ 的儿子 $c$ 转移过来,就算其为空,令 $fail[ch[x][c]]$ 也为空即可
void build() {
    queue <int> q;
    for(int i = 0 ; i < 26 ; ++ i) if(ch[0][i]) fail[ch[0][i]] = 0; q.push(ch[0][i]);
    while(!q.empty()) {
        int x = q.front(); q.pop();
        for(int i = 0 ; i < 26 ; ++ i) {
            if(ch[x][i]) {fail[ch[x][i]] = ch[fail[u]][i]; q.push(ch[u][i]);}
            else ch[x][i] = ch[fail[x][i];
        }
    }
}

匹配方法:

  • 假设现在已经匹配到了节点 $x$ ,接下来匹配字符 $c$
  • 因为构造方法可知 $x$ 必然有儿子 $c$ (有可能向某个有该儿子的最长后缀转移),那么就直接移动至 $ch[x][c]$ ,同时因为可能其他的后缀串也有这个儿子,所以通过 $fail$ 指针去寻找有这个儿子的后缀串并且统计答案
int query(char *s) {
    int now = 0 , l = strlen(s) , res = 0;
    for(int i = 0 ; i < l ; ++ i) {
        int c = s[i] - 'a';
        now = ch[now][c];
        int t = now;
        while(t && ~val[t]) {
            res += val[t];
            val[t] = -1;
            f = fail[t];
            //每个节点只做一次贡献
        }
    }
    return res;
}

题目

BZOJ 2434 [NOI 2011]阿狸的打字机 题解
BZOJ 2754 [SCOI2012]喵星球上的点名 题解

Comments

添加新评论