1. 题目

传送门=￣ω￣=

2. 题解

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

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

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

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

代码：

#include <bits/stdc++.h>
#define NS (200005)
using namespace std;
char s[NS];
int n,N,rc,sa[NS],x[NS],y[NS],T[NS];
void Rsort()
{
    for(int i=1;i<=rc;i++)T[i]=0;
    for(int i=1;i<=n;i++)T[x[y[i]]]++;
    for(int i=1;i<=rc;i++)T[i]+=T[i-1];
    for(int i=n;i;i--)sa[T[x[y[i]]]--]=y[i];
}
int main()
{
    scanf("%s",s+1),n=strlen(s+1);
    for(int i=1;i<=n;i++)s[i+n]=s[i];
    N=n,n<<=1;
    for(int i=1;i<=n;i++)x[i]=s[i]+128,y[i]=i;
    rc=256,Rsort();
    for(int l=1,tmp=1;tmp<n;l<<=1,rc=tmp)
    {
        tmp=0;
        for(int i=n-l+1;i<=n;i++)y[++tmp]=i;
        for(int i=1;i<=n;i++)if(sa[i]>l)y[++tmp]=sa[i]-l;
        Rsort(),swap(x,y),tmp=x[sa[1]]=1;
        for(int i=2;i<=n;i++)
            if(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+l]==y[sa[i-1]+l])x[sa[i]]=tmp;
            else x[sa[i]]=++tmp;
    }
    for(int i=1;i<=n;i++)if(sa[i]<=N)putchar(s[sa[i]+N-1]);
    return 0;
}