题解：[THUWC 2018] 字胡串

_Communist · 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.