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 指针。假设我们要求 号节点的 fail 指针,它的父亲节点是 ,是父亲的 儿子,分以下情况考虑:
-
若 不为空,那么就直接指向 ,即在末尾接上一个字符 。
-
否则已知向上跳 fail,直到能接上为止。
构建方法很想 KMP 算法的求解 的方法,但是我们不能暴力跳,因此实际代码中采用 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 树上的 ,然后暴力跳 fail 即可。询问复杂度暂且不管(往下看)。
AC 自动机拓扑建图优化
以上的题复杂度有保证,一部分是因为 Trie 的深度有保证,一部分是因为访问后的节点可以打上标记不被再次访问。但对于其他题目来说,询问的复杂度可以被卡到 。因此要考虑用拓扑建图来优化。
其实没有想象中的那么难,非常的 naive 啊。我们发现每次到达一个 Trie 树上的节点,都要把它已知跳 fail,给经过的路径上的点全部统计答案,这样很浪费。我们不难想到只要给访问到的点打上标记,然后在完成查询后对 Trie 树做一遍拓扑排序即可。
为什么是拓扑排序:我们把 fail 指针看成一条有向边,不难发现所有边都是由深的节点指向浅的节点,且每个点只有 条出边,因此这张图是一张 DAG,因此可以做拓扑排序。