AC自动机

AC 自动机

AC 自动机是以 Trie 的结构为基础，结合 KMP 的思想建立的。—— OI Wiki

AC 自动机能够用于解决多个模式串匹配的问题。首先是将所有的模式串建成 Trie 树，这个过程是平凡的。接下来是 fail 指针，是 AC 自动机的精华所在，AC 自动机便是借助它来实现多模式串匹配的。

先给出定义：Trie 树上的一个节点的 fail 指针是指向所有模式串的前缀中匹配当前状态的最长后缀。通俗地讲，就是指向 Trie 树上深度最深的，且 表示的字符串前缀 是 当前节点表示的字符串前缀 的后缀的 一个 非当前节点的节点，若没有，则指向根。

如上图，5 号节点代表的字符串前缀是 hi，10 号节点代表的字符串前缀是 i，i 是 hi 的最长的出现过的后缀，因此 5 号节点的 fail 指向 10 号节点。再如 9 号节点代表的字符串前缀是 she，2 号节点代表 he，he 是 she 的最长的出现过的后缀，故 9 号节点的 fail 指向 2 号节点。理解起来还是比较容易的。

接下来考虑求出 fail 指针。假设我们要求 $u$ 号节点的 fail 指针，它的父亲节点是 $fa$，是父亲的 $c$ 儿子，分以下情况考虑：

• 若 $\text{son}_{\text{fail}_{fa},c}$ 不为空，那么就直接指向 $\text{son}_{\text{fail}_{fa},c}$，即在末尾接上一个字符 $c$。

• 否则已知向上跳 fail，直到能接上为止。

构建方法很想 KMP 算法的求解 $nxt$ 的方法，但是我们不能暴力跳，因此实际代码中采用 bfs 的方式，代码如下：

void build(){
  rep(i,0,25) if(t[0].son[i]) t[t[0].son[i]].fail=0,q.push(t[0].son[i]);
  while(!q.empty()){
    int p=q.front(); q.pop();
    rep(i,0,25){
      if(t[p].son[i]) t[t[p].son[i]].fail=t[t[p].fail].son[i],q.push(t[p].son[i]);
      else t[p].son[i]=t[t[p].fail].son[i];
    }
  }
}

很好理解，我们把没有的儿子直接指向的 fail 的儿子，这样就避免了暴力的跳 fail，非常高妙。

接下来看查询。枚举每个前缀，找出当前位置在 Trie 树上的 $\text{idx}$，然后暴力跳 fail 即可。询问复杂度暂且不管（往下看）。

AC 自动机拓扑建图优化

以上的题复杂度有保证，一部分是因为 Trie 的深度有保证，一部分是因为访问后的节点可以打上标记不被再次访问。但对于其他题目来说，询问的复杂度可以被卡到 $O(|S|\max\{|T|\})$。因此要考虑用拓扑建图来优化。

其实没有想象中的那么难，非常的 naive 啊。我们发现每次到达一个 Trie 树上的节点，都要把它已知跳 fail，给经过的路径上的点全部统计答案，这样很浪费。我们不难想到只要给访问到的点打上标记，然后在完成查询后对 Trie 树做一遍拓扑排序即可。

为什么是拓扑排序：我们把 fail 指针看成一条有向边，不难发现所有边都是由深的节点指向浅的节点，且每个点只有 $1$ 条出边，因此这张图是一张 DAG，因此可以做拓扑排序。