AC 自动机

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

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

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

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

接下来考虑求出 fail 指针。假设我们要求 uu 号节点的 fail 指针,它的父亲节点是 fafa,是父亲的 cc 儿子,分以下情况考虑:

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

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

构建方法很想 KMP 算法的求解 nxtnxt 的方法,但是我们不能暴力跳,因此实际代码中采用 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 树上的 idx\text{idx},然后暴力跳 fail 即可。询问复杂度暂且不管(往下看)。

AC 自动机拓扑建图优化

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

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

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