laekov

最初以为是水题，直接写个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);

}