自动搬运

查看原文

来自洛谷，原作者为

	AFewSuns 弱省弱校蒟蒻，tcl，zbl

搬运于2025-08-24 22:46:14，当前版本为作者最后更新于2023-05-04 14:51:11，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

感觉这题出的很好阿，但是评黑有点过了。

题目大意

给定 $n$ 个文本串 $S_i$，有 $m$ 次询问，每次给定两个字符串 $P,Q$，求有多少个文本串同时包含前缀 $P$ 和后缀 $Q$。

$1 \leq n,m \leq 10^5,1 \leq |S_i|,|P_i|,|Q_i| \leq 10^5,1 \leq \sum|S_i|,\sum|P_i|,\sum|Q_i| \leq 2 \times 10^6,|\Sigma|=4$。

题目分析

首先看到题目的第一反应肯定是 $\text{trie}$，如果只有前缀要求的话就是 $\text{trie}$ 树板子了。

不过没关系。考虑到这个板子的前缀查询实际上是求 $\text{trie}$ 树上某个子树内有多少个串，于是对反串也建一个 $\text{trie}$ 树，这样相当于数有多少个串，既在第一棵树的某个子树内，也在第二棵树的某个子树内。

子树问题可以通过 $\text{dfs}$ 序转化成区间问题，于是这就变成了一个经典的二维数点问题：

给定平面上 $n$ 个点，$m$ 次询问一个矩形内有多少个点。

差分后二维数点即可，复杂度 $\mathcal O(\sum|S|+(n+m)\log n)$，这好像也是官方题解的做法。

---

但是强化成二维数点好像很蠢。有没有更好的做法呢？

有！

把反串的那棵 $\text{trie}$ 扔掉，现在只有一开始的 $\text{trie}$。还是将子树转化成区间，那么问题相当于求一段区间 $[l_i,r_i]$ 内有多少个串包含后缀 $Q_i$。

这又是一个经典问题，可以构建可持久化 $\text{trie}$ 来做到 $\mathcal O(\sum|S|)$ 的复杂度。

---

还有没有其他做法？

有！

这次我们不把子树问题转化成区间问题，而是直接在 $\text{trie}$ 树上讨论。一个比较容易想到的做法是对 $\text{trie}$ 树上每个节点都建一棵 $\text{trie}$，用来维护子树内串的后缀信息。

如果直接使用类似线段树套线段树的做法，那么时间空间复杂度双双爆炸。可以将询问离线下来之后 $\text{dsu on tree}$。具体来说，将一个节点的子树大小定义为子树内 $\text{trie}$ 的长度和，那么除去第一次的插入，每次暴力插入一个串时，它所在的节点的子树大小就会至少翻一倍，时间复杂度 $\mathcal O(\sum|S|\log\sum|S|)$。

---

能不能再快一点？

能！

注意到 $\text{dsu on tree}$ 的题一般都可以用线段树合并做，于是类似地，我们使用 $\text{trie}$ 树合并。

类比线段树合并的过程，合并两个 $\text{trie}$ 时，如果当前节点只有一个 $\text{trie}$ 有，那么直接返回；否则一直搜索下去，将两树这个节点的信息合并。

至于时间复杂度，不妨设合并的两棵树大小为 $T_x,T_y$，合并之后的树大小为 $T'$，那么这次合并的时间复杂度就是 $\mathcal O(T_x+T_y-T')$，即 $T_x$ 和 $T_y$ 的重合部分。将所有的 $\text{trie}$ 树合并复杂度加起来，那么 $-T'$ 会在它合并的时候与 $+T'$ 抵消掉，最后的复杂度就是所有叶子的 $\text{trie}$ 树大小和减去根的 $\text{trie}$ 树大小。而所有叶子的 $\text{trie}$ 树大小和就是 $\sum|S|$，所以时间复杂度就是 $\mathcal O(\sum|S|)$ 的了！

---

能不能不用 $\text{trie}$？

能！

回到最初的问题，我们需要同时匹配前缀和后缀。这很麻烦，因为前缀和后缀中间可能会有空隙，甚至可能重合，导致一般解决匹配问题的方法都不可行。

既然如此，我们就把它强行“拼接”起来，把一个串 $S_i$ 变成 $S_i\#S_i$，其中 $\#$ 是一个特殊字符。再把需要匹配的前缀 $P_i$ 和后缀 $Q_i$ 变成 $Q_i\#P_i$，那么 $S_i$ 能匹配这个前缀和后缀，就相当于 $S_i\#S_i$ 能匹配 $Q_i\#P_i$ 这个子串。

将所有的 $S_i\#S_i$ 拼接起来，为了避免跨串匹配，在 $S_i$ 与 $S_{i+1}$ 中间插入另一个特殊字符 $\&$，那么原问题就相当于给定 $m$ 个模式串，问它在一个大文本串里出现多少次，使用 AC 自动机即可做到 $\mathcal O(\sum|S|)$。

做法比较多，就不贴代码了。

最后感谢

他就没有这篇博客。