Mike and Friends 题解

思路

把所有字符串插入 AC 自动机。对模式串 $s_k$ 的终止节点记为 $v_k$。扫描任意字符串 $s_i$ 时，每到达一个自动机状态 $u$，所有在失配树上是 $u$ 祖先的终止节点都对应一次以当前位置结尾的匹配。因此 $call(i,k)$ 等于扫描 $s_i$ 时落在失配树子树 $v_k$ 内的状态次数。

对失配树做 Euler 序，子树变成连续区间。把询问拆成两个前缀事件：在处理完字符串 $r$ 后查询一次，在处理完字符串 $l-1$ 后查询一次并取负。按字符串编号递增处理；扫描当前字符串时，把每次到达状态的 Euler 位置在 Fenwick 树中加一。事件查询终止节点子树区间和，即得到对应前缀中该模式串的出现总次数。

做法

1. 插入所有 $s_i$，记录每个字符串的终止节点。
2. BFS 构建失配指针与完整自动机转移，并建立失配树。
3. 迭代遍历失配树得到每个节点的 Euler 进入、离开时间。
4. 将每个询问 $(l,r,k)$ 拆为时刻 $r$ 的正事件和时刻 $l-1$ 的负事件。
5. 顺序扫描各字符串，把经过的状态在 Fenwick 树上单点加一；处理当前时刻事件时查询 $v_k$ 的子树和。

证明

AC 自动机扫描到某位置时，当前状态沿失配指针向根的链恰好是所有以该位置结尾且属于 Trie 的字符串。故模式串 $s_k$ 在 $s_i$ 中的每次出现，与扫描 $s_i$ 时访问失配树子树 $v_k$ 中某个状态一一对应。

处理完前 $x$ 个字符串后，Fenwick 树在每个 Euler 位置保存这些字符串扫描过程中访问对应状态的总次数。子树区间和因此等于 $\sum_{i=1}^{x}call(i,k)$。询问的正事件减负事件得到前缀 $r$ 与前缀 $l-1$ 之差，正好是 $\sum_{i=l}^{r}call(i,k)$。所以所有答案正确。

复杂度

令 $L=\sum |s_i|$。时间复杂度为 $O((L+q)\log L+26L)$，空间复杂度为 $O(L+q+n)$。