【题解】P9196 [JOI Open 2016] 销售基因链

· · 题解

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

题目大意

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

### 题目分析 首先看到题目的第一反应肯定是 $\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|)$。 做法比较多，就不贴代码了。 最后感谢 @[KHIN](https://www.luogu.com.cn/user/236807) 大佬，没有他就没有这篇博客。