最初以为是水题，直接写个dq交上去不对。
看了下题解才知道是后缀数组。好久不写都快不会写了。
把原串倒过来扔一起排一下就行了。
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 60009;
int n;
int sa[maxn], rk[maxn], ro[maxn], w[maxn], o[maxn];
char a[maxn];
void sufixArray(int n) {
memset(w, 0, sizeof(w));
for (int i = 0; i < n; ++ i)
++ w[(int)a[i]];
for (int i = 1; i < 123; ++ i)
w[i] += w[i - 1];
for (int i = 0; i < n; ++ i)
sa[-- w[(int)a[i]]] = i;
rk[sa[0]] = 0;
for (int i = 1; i < n; ++ i)
if (a[sa[i]] == a[sa[i - 1]])
rk[sa[i]] = rk[sa[i - 1]];
else
rk[sa[i]] = rk[sa[i - 1]] + 1;
for (int l = 1; l < n; l <<= 1) {
for (int i = 0; i < n; ++ i)
ro[i] = rk[i];
for (int i = 0; i < n; ++ i)
o[i] = (sa[i] + n - l) % n;
memset(w, 0, sizeof(w));
for (int i = 0; i < n; ++ i)
++ w[rk[i]];
for (int i = 1; i < n; ++ i)
w[i] += w[i - 1];
for (int i = n - 1; i >= 0; -- i)
sa[-- w[ro[o[i]]]] = o[i];
rk[sa[0]] = 0;
for (int i = 1; i < n; ++ i)
if (ro[sa[i]] == ro[sa[i - 1]] && ro[(sa[i] + l) % n] == ro[(sa[i - 1] + l) % n])
rk[sa[i]] = rk[sa[i - 1]];
else
rk[sa[i]] = rk[sa[i - 1]] + 1;
}
}
int main() {
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
#endif
scanf("%d", &n);
for (int i = 0; i < n; ++ i) {
int d;
while (!isupper(d = getchar()));
a[i] = d;
a[n * 2 - i] = d;
}
a[n] = 0;
a[n * 2 + 1] = 32;
sufixArray(n * 2 + 1);
for (int i = 0, j = n - 1, c = 0; i <= j;) {
if (a[i] < a[j])
putchar(a[i ++]);
else if (a[j] < a[i])
putchar(a[j --]);
else if (rk[i] < rk[n * 2 - j])
putchar(a[i ++]);
else
putchar(a[j --]);
if (++ c == 80) {
putchar(10);
c = 0;
}
}
putchar(10);
}