自动搬运

查看原文

来自洛谷，原作者为

	_Communist 面朝大海，春暖花开。

搬运于2025-08-24 23:04:41，当前版本为作者最后更新于2025-02-05 17:27:15，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

目前应该可以通过所有 hack。如果讲的有问题或者代码被 hack 了叫我一声。另外如果有不用哈希的确定性算法也叫我一声谢谢。

首先有一个很 naive 的方案：取 $j=n$，即 $A+B$。这样多半不是最优，但是提供了一个初始方案来做比较，这样字典序大于等于这个方案是没有用的。下面的讨论全部基于这个前提。

考察 $A_{1,j}+B$ 的部分。前面 $j$ 个字符相同，又有字典序比初始方案更小的前提，一定存在 $i$ 满足 $B_i < A_{i+j}$。特别地，令 $A_{n+1}$ 为无限大，就保证上面的条件一定成立。

数据范围不支持我们枚举 $j$，枚举 $i$ （满足 $\forall k<i, B_k=A_{k+j}$ 但 $B_i<A_{i+j}$）找对应最小的 $j$，由于有大小关系，直接在 $A$ 上找对应的一段 $A_{j+1,i+j}$ 并不好做。字符集很小，考虑枚举 $c(>B_i)$ 对应 $A_{i+j}$，转变为字符串匹配，在 $A$ 里面找 $B_{1,i-1}+c$ 的最早出现位置。用 SAM 维护子串匹配即可。

这样就得到了所有可能的方案（最多 $\min(10|B|,n)$ 种），要比较这些方案的大小，可以用哈希+二分找到第一个不同的位置，然后比较这个位置。事实证明这个上界很宽松，而且即使数据卡着造也不会 TLE。

另外（不追求效率可以略过此段），由于 $i+j$ 表示该方案与 $A$ 第一个不同的位置（如果前 $n$ 个字符与 $A$ 相同有 $i+j=n+1$），只有 $i+j$ 最小的方案是有用的，可以进一步加速。

这样求出了最优方案的最终串。此外，题目要求我们使得 $j$ 最小，但在 SAM 上查出来的不一定是最小的。要将 $B$ 尽可能向左移且不改变方案形成的最终串，有必要条件：左移的长度 $len$ 一定是 $B$ 的 period（周期，与 border 互补）的倍数，这很容易证明。所以倍增向左移就可以了。（写这篇题解时的数据很水，只判必要条件都能过）

最后总结一下：先对 $A$ 建 SAM，枚举 $(i,c),c>B_i$，在 SAM 上查对应的一个 $\operatorname{endpos}$，用哈希+二分找出最优方案，最后倍增向左移动 period 的整数倍。

Code.