题解：AT_arc151_e [ARC151E] Keep Being Substring

· · 题解

题目传送门

首先你贪心的去考虑肯定是把 X 消成 X 与 Y 的最长公共子串，然后在加成 Y。

然后最长公共子串可以直接二分答案加哈希做到 O(n \log n)，当然也可以 SAM 做到 O(n)，注意给所有点的哈希值映射为一个随机值不然会被卡。

但是这个题有个很神秘的限制就是你不能把 X 消空，所以考虑 X 和 Y 最长公共子串为空的情况。

这时 X 的所有字符最后都不会留下来，而留下一个字符向外扩展显然比留下 X 的一个子串向外扩展容易。因此最优的方案一定是先把 X 删到只剩一个字符，再把这个字符移动到一个 Y 中有的字符，然后扩展到 Y。

于是可以把 A_i 与 A_{i+1} 之间连边，以所有 X 中的字符为起点，所有 Y 中的字符为中点，求出最短路即可。

时间复杂度 O(n \log n)。

submission