「十二省联考 2019」字符串问题（后缀数组 + 线段树）

题目大意

「十二省联考 2019」字符串问题（Luogu 5284）

题太长了，自己读吧 QAQ。

令 $n = \vert S \vert$，则：

• 对于 $40 \%$ 的数据，$n_a \times n_b \le 2 \times 10^5$。
• 对于 $80 \%$ 的数据，$\vert A_i \vert \ge \vert B_i \vert$。
• 对于 $100 \%$ 的数据，$n, n_a, n_b, m \le 2 \times 10^5$。

思路分析

算法一

直接借助 Hash 暴力建图，做拓扑排序后 DP 求最长链即可。

时间复杂度 $O(n + n_a \times n_b + m)$，期望得分 $40$ 分。

算法二

可以发现复杂度的瓶颈在于 “如果 $B_j$ 是 $A_i$ 的前缀，则从 $B_j$ 向 $A_i$ 连一条边” 这一部分。如果有 $\vert A_i \vert \ge \vert B_i \vert$，那么连边的条件等价于：

$$\text{lcp}(\text{Suf}(L_{a_i}), \text{Suf}(L_{b_j})) \ge \vert B_j \vert$$

对于串后缀排序，则 $B_j$ 对应的 $A$ 就会形成一段区间。这段区间可以通过在 $\text{height}$ 数组上倍增来找到。找到区间以后，我们使用线段树优化建图即可。

我们将 $n, n_a, n_b, m$ 看作同阶，时间复杂度 $O(n \log n)$，期望得分 $80$ 分。

算法三

如果不保证 $\vert A_i \vert \ge \vert B_i \vert$，那么连边的条件就多了一个，也就是增加了一维的限制。我们使用主席树来代替线段树优化建边即可。

我们将 $n, n_a, n_b, m$ 看作同阶，时间复杂度 $O(n \log n)$，期望得分 $100$ 分。

代码实现

#include <cstdio>