题解：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)$。