字符串匹配的AC自动机，你知道有哪三种写法吗？

法一

空间复杂度 \(O(n|\Sigma|)\)，时间复杂度 \(O(n|\Sigma|)\)，查询单步严格 \(O(1)\)。
大家最常见的写法。直接 bfs 递推求出 fail，用静态数组存儿子。

法二

空间复杂度 \(O(n)\)，时间复杂度 \(O(\sum |s|)\)，查询均摊 \(O(\sum|q|)\)。
建 fail 的时候模仿 KMP，从父亲的 fail 开始，如果存在对应出边则自己 fail 指过去，否则跳 fail。查询同样暴力跳 fail。trie用哈希表/umap 存。

法三

空间复杂度 \(O(n\log |\Sigma|)\)，时间复杂度 \(O(n\log |\Sigma|)\)，查询单步严格 \(O(\log |\Sigma|)\)。
注意到法一中所需支持的操作是，复制父亲的fail，在自己的fail里单点改少量位置。因此直接可持久化线段树维护儿子即可。