Aho-Corasick automaton

本文基本上是oiwiki的复制粘贴:https://oi-wiki.org/string/ac-automaton/

可能加上了自己感性理解

概述

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

建立AC自动机有两个步骤:

  • TRIE:将所有的模式串构成一颗字典树
  • KMP:对TRIE上所有的状态构造失配指针

可以说,AC自动机是由字典树和失配指针构成的

回顾KMP

  • KMP匹配算法可以在线性时间内判定字符串\(A[1-N]\)是字符串\(B[1-M]\)的子串,并求出字符串A在字符串B中各次出现的位置.有两个数组:\(next,f​\)
  • \(next[i]​\)表示的是A中以i为结尾的非前缀子串A的前缀能够匹配的最长长度
  • \(f[i]​\)表示的是B中以i为结尾的子串A的前缀能够匹配的最长长度

一直说AC自动机就是树上的KMP,那这两者有什么关系呢?

字典树insert()

字典树上的每个节点代表有限自动机一个状态,表示的是某个模式串的前缀。

编译原理学得超级差..(

模式串的结尾状态被称为可接受状态

字典树的插入:

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]++;
}

失配指针fail[]

AC自动机需要利用一个fail指针来辅助多模式串的匹配

状态\(u\)的fail指针指向另一个状态\(v\)\(v\)\(u​\)的最长后缀。这里的fail指针跟KMP的next指针一样是在失配的时候使用,fail指针指向的是所有模式串的前缀中匹配当前状态的最长后缀。AC 自动机在做匹配时,同一位上可匹配多个模式串。因为有多个模式串,所以会指向多个模式串中的一个.KMP算法只有一个模式串,不会指向另一个模式串.

如果模式串只有一个,是不是相当于KMP算法?

考虑字典树中当前结点\(u\)\(u\)的父节点是\(p\)\(p\)通过字符c的边指向\(u\),标记为\(tr[p,c]=u\)

假设深度小于\(u​\)的所有结点的fail指针构造完毕

  • \(tr[fail[p],c]\)存在:则让\(u\)的fail指针指向\(tr[fail[p],c]\)。即在\(p\)\(fail[p]\)后面加一个字符c,对应\(u\)\(fail[u]\)
  • \(tr[fail[p],c]\)不存在: 则继续找到\(tr[fail[fail[p],c]]]​\)。重复1的判断过程
  • 如果真的没有,就让fail指针指向根结点

构建函数build()

build()的目标有两个:一个是构建fail指针,一个是构建自动机

  • \(tr[u,c]\)表示从当前状态\(u\)后面加一个字符c能到达的状态,即一个状态转移函数
  • q队列,用于BFS遍历字符串
  • \(fail[u]​\)结点\(u​\)的fail指针
    queue<int> q;

    void build() {
        for (int i = 0; i < 26; ++i){
            if (tr[0][i]) {
                q.push(tr[0][i]);
            }
        }
        while (!q.empty()) {/*每次从队列中取出的u,表示fail[u]已经求出*/
            int u = q.front();
            q.pop();
            for (int i = 0; i < 26; ++i) {
                if (tr[u][i]) {/*这里表示的就是1过程,一行代码搞定*/
                    fail[tr[u][i]] = tr[fail[u]][i];
                    q.push(tr[u][i]);
                } else {
                    tr[u][i] = tr[fail[u]][i];/*这行代码会改变树的结构,因为改变了tr数组,好处是节省时间,不需要跳那么多次fail,可以理解为路径压缩,直接到下一个能匹配的位置*/
                }
            }
        }
    }

fail指针的作用可以理解为舍弃前缀,指向下一个匹配的位置.

现在可能有个问题是对于kmp而言,那个板子求next是需要一个while循环,但是ac自动机的这个板子求fail只需要一行代码.

我查过存在递归查找的板子,本文板子我的感性理解应该是因为空间换时间,将trie树变成图 ,采用了递推的方法.

多模式匹配query()

既然建好了图,也就是ac自动机,直接把字符串t输入到自动机去.

利用fail指针找出匹配的模式串.

在匹配字符串的过程中,我们会舍弃部分前缀达到最低限度的匹配.

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;
}

模板

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.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];
                }
            }
        }
    }

    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;
    }
}