自动搬运

查看原文

来自洛谷，原作者为

	sunkuangzheng **

搬运于2025-08-24 22:50:32，当前版本为作者最后更新于2024-04-09 08:24:17，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

$\textbf{P9664}$

• 给定 $n$ 个字符串 $s_1,s_2,\ldots,s_n$，构造 $n$ 个点的无向完全图 $G$，边 $i,j$ 的边权是 $\operatorname{LCS}(s_i,s_j)$，其中 $\operatorname{LCS}$ 指最长公共子串。
• 求 $G$ 的最大生成树边权和。
• $1 \le n,\sum |s_i| \le 2 \cdot 10^6$。

后缀数组做这题应该是最简单的吧。

回忆一下我们是怎么用 SA 求两串 $\operatorname{LCS}$ 的，我们是直接拼起来，然后枚举 $rk$ 相邻的归属串不同的两个后缀计算 $\operatorname{LCP}$ 后取 $\max$。

把所有 $s_i$ 拼起来用不同的分隔符隔开，我们有结论有用的边只有 $(sa_i,sa_{i+1})$ 这 $\mathcal O(\sum |s_i|)$ 条。考虑一条边 $(sa_i,sa_{i+k}) \; (k \ge 2)$，其边权等于 $(sa_i,sa_{i+1}),\ldots,(sa_{i+k-1},sa_{i+k})$ 边权的最小值，我们在 Kruskal 合并的过程中一定会先把中间的边都考虑完，而此时 $sa_i,sa_{i+k}$ 必然已经连通，因此 $(sa_i,sa_{i+k})$ 这条边没有用。

令 $m = \sum |s_i|$，时间复杂度 $\mathcal O(m \log m)$。