将字符串翻转后接到原串的后面，中间加一个分隔符，每次都贪心选择rank小的那个

事实上就是练习一发后缀数组的模板

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<vector>

#include<cstdio>

#include<queue>

#include<cmath>

#include<set>

#include<map>

#define inf 0x7FFFFFFF

#define ll long long

#define N 1000005

using namespace std;

char get()

{

    char c=getchar();

    for(;c>'Z'||c<'A';c=getchar());

    return c;

}

char s[N];

int t1[N],t2[N],cc[N],sa[N],rank[N];

int n,m,len;

bool cmp(int *y,int a,int b,int k)

{

    int a1=y[a],b1=y[b];

    int a2=a+k>=len?-1:y[a+k];

    int b2=b+k>=len?

-1:y[b+k];

    return a1==b1&&a2==b2;

}

void make_sa()

{

    int *x=t1,*y=t2,m=2666;

    for(int i=0;i<len;i++)cc[x[i]=s[i]]++;

    for(int i=1;i<m;i++)cc[i]+=cc[i-1];

    for(int i=len-1;~i;i--)sa[--cc[x[i]]]=i;

    for(int k=1;k<len;k<<=1)

    {

        int p=0;

        for(int i=len-k;i<len;i++)y[p++]=i;

        for(int i=0;i<len;i++)

            if(sa[i]>=k)y[p++]=sa[i]-k;

        for(int i=0;i<m;i++)cc[i]=0;

        for(int i=0;i<len;i++)++cc[x[y[i]]];

        for(int i=1;i<m;i++)cc[i]+=cc[i-1];

        for(int i=len-1;~i;i--)sa[--cc[x[y[i]]]]=y[i];

        swap(x,y);x[sa[0]]=0;m=1;

        for(int i=1;i<len;i++)x[sa[i]]=cmp(y,sa[i],sa[i-1],k)?

m-1:m++;

        if(m>len)break;

    }

    for(int i=0;i<len;i++)rank[sa[i]]=i;

}

int main()

{

    scanf("%d",&n);s[n]='$';len=2*n+1;

    for(int i=0;i<n;i++)

        s[2*n-i]=s[i]=get();

    make_sa();

    int l=0,r=n-1;

    for(int i=1;i<=n;i++)

    {

        if(rank[l]<rank[2*n-r])

            putchar(s[l++]);else putchar(s[r--]);

        if(i%80==0)puts("");

    }

    return 0;

}