自动搬运

查看原文

来自洛谷，原作者为

	MrPython waac_tXKCMem1dAph0gg0

搬运于2025-08-24 23:11:01，当前版本为作者最后更新于2025-08-07 21:04:07，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

做个题给我气笑了，难点在于读题。

考虑字符串的所有 $s$ 所有前缀所构成的集合 $p_s = \{s_{1:i} | 0 \leq i \leq \left|s\right| \}$。由于 $\operatorname{border}(t)$ 是 $t$ 的前缀，显然有 $t \in s \Rightarrow \operatorname{border}(t)\in s$。将 $s$ 中的每个元素视为图上的点，并对于所有满足 $t \in s \wedge t \neq \varepsilon$ 的字符串 $t$ 在图上添加边 $t \leftrightarrow \operatorname{border}(t)$，则整张图会构成一颗以 $\varepsilon$ 为根的树。

用 $s$ 的前缀 $x$ 生成的前缀集合 $u$ 也要求 $t \in s \Rightarrow \operatorname{border}(t)\in s$，则 $u$ 显然是 $s$ 的子集，用刚才的方式生成的图即为树上 $x$ 到跟 $\varepsilon$ 的链。$g(x,y)$ 则是图上 $x$ 和 $y$ 的 LCA。因此，最后合并后的集合是树上 $x$ 到 $y$ 路径上的点所构成的集合。

然后你发现这其实是点分治板子，然后就做完了。