BZOJ 1692 [Usaco2007 Dec] 队列变换

发布于 2017-07-14  201 次阅读


题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1692

题意:一个串,每次可以从前面或者后面拽出来一个放到新串头,求最小字典序新串。


朴素的贪心思路是非常简单的,即每次都选头和尾中最小的那个。

如果相同怎么办呢?暴力的话就是判断下一位,直到不同为止,然而复杂度无法保证

考虑我们要的实际上是什么:比较一个前缀串和一个后缀串的字典序,如果都是后缀串显然直接 SA,前缀怎么办呢?

有一个很妙的方法:将原串翻转一遍接在后面,这样后半段就是用后缀串表示的前缀串了。

大小一定在两半串分割之前比较出来,若比较出不来,相等的情况随便选啦

这样的话,对新串求 rank 就可以了。每次不单纯的判断头和尾的字典序,而是判断头在前半后缀的 rank 和尾在后半后缀的 rank。时间复杂度\(O(nlog_n)\)(只会倍增 qwq

 

 


一个非常弱的准退役OIER