重学了 AC 自动机，搞懂了。

AC 自动机

NOI2011 阿狸的打字机

注意到询问的全部都是树边，所以并不会出现某个位置跳着跳着就走了 $fail$ 指针。

那么就很简单了，我们相当于给 $trie$ 树进行单点修改，然后在 $fail$ 树上进行子树查询。

那么我们把 $fail$ 用 dfs 序拍成一个数组，然后我们把询问离线下来。

有一种在树上处理所有链的方法，即在树上进行 dfs，在进入某个点是把贡献记录下来，然后在离开这个点的时候把贡献删除掉。

这样我们不论在哪里，当下的贡献都是从 $rt$ 到 $x$ 这个位置贡献的。

那么如果在 $trie$ 树上跑这个操作，然后直接在 $fail$ 树上进行区间查询即可，时间复杂度为 $O(n\log n)$，其中 $O(\log n)$ 来自树状数组。

COCI 2015 Divljak

需要注意，我们这里求解的是出现 $s_x$ 的 $T$ 中元素的数量，而并非次数，这有本质区别。

换而言之，我们的操作相当于在 $fail$ 树上选择若干点，然后把这些点到 $rt$ 的路径全部设置为 $1$。

那么我们直接多选择 $rt$，把他们按照 dfs 序排序，然后把相邻的路径设置为 $1$，最后询问的时候整体除以 $2$ 就行了。

套路题，时间复杂度是线性对数的。

JSOI2007 文本生成器

题目复杂不可读，下面是人话：给定 $n$ 个模式串，求至少包含 $1$ 个模式串的长度为 $m$ 的文本串。

考虑容斥，统计有几个串不包含任意一个模式串。

直接把 $fail$ 子树里面全部标记一遍，直接设 $f_{i,j}$ 表示考虑到了第 $j$ 个点串长为 $i$ 的情况下不经过标记过的点的方案数。

随便转移即可，时间复杂度为线性。

SDOI2014 数数

上一题加强版，数位 DP 即可。