fail 数上的子树更改或查询是易于维护的，而对一个字符串在 AC 自动机上经过的路径进行更改或查询只能暴力做。

所以如果直接把 CF547E 的做法用到这里来，区间询问拆成前缀，对每个前缀按顺序处理，fail 树上子树加，每个询问在 AC 自动机上暴力求和，时间复杂度为 $O(A\sum|s_i|+B\sum|s_{t_i}|)$。其中 $t_i$ 为第 $i$ 次询问的文本串，$A$ 为区间加的时间复杂度，$B$ 为单点查询的时间复杂度。注意式子中第一个 $\sum$ 是有约束的（不超过 $10^5$），而第二个没有。这样我们就获得了一个与文本串串长相关的暴力做法。

注意到第一个做法的问题在于遍历文本串的次数过多。如果选择每个文本串只进行一次遍历，对经过的所有点做 $O(1)$ 子树加（树上前缀和），然后依此处理该文本串相关的所有询问，这个做法的时间复杂度为 $O(\sum|s_{t_i}|+|t|\sum|s_i|)$，$t$ 为询问的文本串序列。

于是我们根号分治：对于长度不超过 $\sqrt{\sum|s_i|}$ 的串使用第一种算法，使用 $A=O(\sqrt n),B=O(1)$ 分块进行区间加单点查；否则使用第二种算法，此时 $|t|=O(\sqrt{\sum|s_i|})$。总时间复杂度为 $O((\sum|s_i|)^{1.5})$

对所有串建出 AC 自动机，如果能够找到一个不经过终止状态的环，则存在一条无限长的不包含所有模式串的 01 串。

给定多个字符串，多次询问 $x$ 串在 $y$ 串中出现了多少次。

$x$ 在 $y$ 中的每次出现都恰对应 AC 自动机上的一个节点，使得这个节点为 $y$ 的前缀（在 Trie 树上为 $y$ 的祖先），并且这个节点存在后缀 $x$（在失配树上为 $x$ 的后代），这个点即结尾于该次出现的右端点的前缀。

也即我们需要查询 Trie 树上从根到 $y$ 这一条路径上，有多少在失配树上以 $x$ 为根的子树内。于是用树状数组根据 dfs 序维护子树和，在 Trie 树上 dfs，动态维护当前所在的点到根这一条路径上所有点，在树状数组上做单点加减，区间求和。

做法

核心在于维护失配指针，即每个节点指向 Trie 中存在的最长真后缀。

先建出 Trie 树。将根节点的后继节点加入作为起始节点 bfs。

bfs 的过程中，对于当前节点遍历字符集中的每个字符 $c$。

• 如果 $u$ 存在转移 $c$，那么这条转移的终点的失配指针应当指向 $u$ 的失配指针指向的节点向 $c$ 转移的结果，然后将这条转移的终点加入 bfs 队列。
• 如果 $u$ 不存在转移 $c$，那么新建一条向 $c$ 转移至 $u$ 的失配指针指向的节点向 $c$ 转移的结果。

不难发现从一个节点走向它失配指针指向的位置，它所代表的字符串的长度单调减少。因此从一个节点一直这样走，最后一定能够走到 Trie 的根节点。于是失配指针的关系构成了有根一棵树，以每个节点为根的子树即以这个节点为后缀的所有节点。