先设 $|S|$ 为一个模式串长度， $|\sum_S|$ 为模式串总长，$|\sum|$ 为字符集大小，$|T|$ 为一个文本串长度， $n$ 为 $trie$ 树点的个数

AC 自动机有两种 $getfail$ 的方式：

方法一：每个点都访问的所有字符集元素，若无此儿子则赋值为 $ch_{fail_x,i}$ ，若有儿子直接 $fail_{ch_{x,i}} = ch_{fail_x,i}$ 。这样路径压缩，匹配时跳 $fail$ 的次数会减少，但 $getfail$ 的复杂度至少 $|\sum||\sum_S|$ 。

方法二：暴力跳 $fail$ 直到第一个存在 $ch_{y,i}$ 的 $y$ 。我们来分析这个复杂度。

1.对于 $getfail$ ，看起来跳的很多，但我们考虑每个模式串（一条链），儿子的 $fail$ 一定是接着它父亲跳的，而跳一次深度就要 -1，所以一条链跳 $fail$ 复杂度 $\le \Theta(|S|)$ ，全部点跳 $fail$ 的复杂度 $\le\Theta(|\sum_S|)$ ，没问题。

2.对于 $bfs$ ， 仍然访问0~25每个节点会炸，所以用个 $vector$ 存一下就做到 $\Theta(n) < \Theta(|\sum_S|)$ ，也没问题。

3.对于匹配的状态转移，虽然每次在失配时不能直接转移，而是要一直跳 $fail$ ，但同上，跳 $fail$ 至少使深度-1，所以复杂度 $\Theta(|T|)$ 仍然没问题。

4.对于匹配时计算贡献时跳的 $fail$，只需打 $ed = -1$ 的标记就还是 $\Theta(|T|)$ ，没问题。

综上，方法一优化了匹配转移的常数，但增加了 $getfail$ 的复杂度，而此题是单文本串，按理来说方法二会爆杀方法一……

但我测的结果是方法二竟然慢1.5倍？？？

方法一评测记录 206ms

方法二评测记录 298ms

为什么捏qwq

vector 不至于慢 39 倍吧