算法课读书笔记之字符串算法学习体会及其应用-AC自动机

另一个问题的提出

我们注意到KMP算法所能优化的是一种单模式串的匹配,那么考虑多模式串的匹配下,KMP算法的复杂度是多少呢？显然，对于每个模式串,我们都要进行一次KMP算法,当有k个模式串时,它们的长度分别是m1,m2....mk,那么我们需要做k次KMP算法,时间复杂度是 $O(\sum\limits_{i = 1}^{k}(n + m_i)) = O(n * k +\sum\limits_{i = 1}^{k}m_i)$
此时复杂度不再优秀。基于这个问题,我们来讨论下一种适用于多模式串匹配的算法——AC自动机。

AC自动机——一种多模式串匹配算法[^2]

什么是AC自动机？

Aho-Corasick automaton，简称AC自动机,该算法在1975年产生于贝尔实验室，是著名的多模匹配算法。初次接触AC自动机这个名词,会感觉很陌生和遥远,自动机是有限状态机(FSM)的数学模型,在离散数学中我曾经接触过类似的概念,但因为课程教学的侧重点不在于此,我也没有深入研究。
我对于自动机的理解是把输入的数据根据转移函数不断进行状态的转移,直到所有数据被读取完毕。关于AC自动机,首先我们需要对字典树(Trie)和KMP算法有一定理解。AC自动机,就是在Trie树的基础上,增加一个fail指针,如果当前点匹配失败,则将指针转移到fail指针指向的地方,这样就不用回溯,而可以一路匹配下去了。

const int N = 5e5 + 5;
struct Trie{ 
  int nextz[N][26], fail[N], endz[N]; 
  int root, L;
  int newnode(){
    for(int i = 0; i < 26; i++){
      nextz[L][i] = -1; 
    }
    endz[L++] = 0; 
    return L - 1;
  }
  void init(){
    L = 0, root = newnode();
  }
  void insert(char buf[]){ // 插入操作 与字典树一样
    int len = strlen(buf); 
    int now = root;
    for(int i = 0; i < len; i++){
      if(nextz[now][buf[i] - 'a'] == -1){
        nextz[now][buf[i] - 'a'] = newnode(); // 建立新节点
      }
      now = nextz[now][buf[i] - 'a']; // 遍历下一个节点
    }
    endz[now]++; // 以该点结束的单词增加1
  }
  void build(){ // 建立fail指针
    queue<int> Q;
    fail[root] = root;
    for(int i = 0; i < 26; i++){
      if(nextz[root][i] == -1){
        nextz[root][i] = root;
      }
      else {
        fail[nextz[root][i]] = root;
        Q.push(nextz[root][i]);
      }
    }
    while(!Q.empty()){
      int now = Q.front();
      Q.pop();
      for(int i = 0; i < 26; i++){
        if(nextz[now][i] == -1){ // 没有出现过这个字符
          nextz[now][i] = nextz[fail[now]][i]; // 跳到fail指针所指节点
        }
        else {
          fail[nextz[now][i]] = nextz[fail[now]][i]; // 父亲fail指针的下一个对应相同字符
          Q.push(nextz[now][i]);
        }
      }
    }
  }
  int query(char buf[]){
    int len = strlen(buf);
    int now = root;
    int res = 0;
    for(int i = 0; i < len; i++){
      now = nextz[now][buf[i] - 'a'];
      int temp = now;
      while(temp != root){
        res += endz[temp]; 
        endz[temp] = 0; // 标记为0 防止重复计算
        temp = fail[temp];
      }
    }
    return res;
  }
};

时间和空间复杂度分析

先看空间复杂度,这个比较好分析,我们注意到AC自动机需要建立一个Trie,设字符集大小为k, 模式串总长度 $\sum\limits_{i = 1}^{m}len(t_{i}) = M$ , 则总的空间复杂度是 $O(kM)$ ,因为字符集k通常是一个常数,因此也可以认为空间复杂度是 $O(M)$
考虑时间复杂度,我们建立一个Trie,插入的时候遍历了每一个模式串,复杂度为 $O(M)$ 考虑建立fali指针过程遍历了全部模式串,复杂度为 $O(M)$ ,而我们整个匹配过程需要遍历整个主串,复杂度为 $O(n)$ ,因此总体时间复杂度是 $O(n + m)$
[^2]: 参考博客 https://bestsort.cn/2019/04/28/402/