题解 P5329 【[SNOI2019]字符串】

2019-05-01 08:16:56


考虑怎么比较 $s_i$ 和 $s_j$ 的大小。

发现, $s_i$ 和 $s_j$ 的前面是一样的,后面也是一样的,不一样的只有中间一部分。

那么我们只要比较这一段的大小就好了。

要比大小的话,显然需要求出 $\mathrm{LCP}$ 。

注意到两个后缀正好错开一位,那么我们只要知道后缀 $i$ 和后缀 $i+1$ 的 $\mathrm{LCP}$ 即可。这个可以 $O(n)$ 递推出来。 当然SA也是可以的

然后直接 $\mathrm{stable\_sort}$ 即可。

具体实现及细节见代码