1. 题目

传送门= ̄ω ̄=

2. 题解

因为把字符串接成了一个环,所以我们把字符串复制一遍以后接在原字符串后面。
(比如abc变成abcabc)

接着我们求出复制后的字符串的后缀数组$SA$。

最后依次输出$str[SA[1,n]]$就行了。

这里要注意一下:$str$指的是复制后的字符串,$n$指的是$str$的长度,而且需要判断,只有当$SA[i]\leq n\div 2$的时候才输出$str[SA[i]]$

代码: