bclgold

#include <iostream>
#include <fstream>

#include <string>
#include <algorithm>

#include <cassert>

using namespace std;

const int MAXN = 30000 + 5;

struct sort_fst {
    const string& s;
    sort_fst(const string& s) : s(s) {}
    bool operator()(int i, int j) { return s[i] < s[j]; }
};

int N;
string S;

int r, rs[2*MAXN], rk[2][2*MAXN], pw, sa[2*MAXN], sa2[2*MAXN];

int main() {
    ifstream fin("bclgold.in");
    ofstream fout("bclgold.out");

    fin >> N;
    for (int i = 0; i < N; ++i) {
        string ch;
        fin >> ch;
        S += ch;
    }

    string conc = S + '$' + string(S.rbegin(), S.rend());
    int n = N + 1 + N;

    for (int i = 0; i < n; ++i) sa[i] = i;
    sort(sa, sa+n, sort_fst(conc));
    r = 0;
    for (int i = 1; i < n; ++i) {
        if (conc[sa[i]] != conc[sa[i - 1]])
            rs[++r] = i;
        rk[0][sa[i]] = r;
    }

    for (int l = 1; l < n; pw ^= 1, l <<= 1) {
        for (int i = n - l; i < n; ++i)
            sa2[rs[rk[pw][i]]++] = i;
        for (int i = 0; i < n; ++i)
            if (sa[i] >= l)
                sa2[rs[rk[pw][sa[i] - l]]++] = sa[i] - l;

        r = 0;
        rk[pw^1][sa[0] = sa2[0]] = 0;
        rs[0] = 0;
        for (int i = 1; i < n; ++i) {
            if (rk[pw][sa2[i]] != rk[pw][sa2[i-1]] ||
                sa2[i]+l >= n || sa2[i-1]+l >= n ||
                rk[pw][sa2[i]+l] != rk[pw][sa2[i-1]+l])

                rs[++r] = i;
            rk[pw^1][sa[i] = sa2[i]] = r;
        }
    }

    int i = 0, j = N + 1;
    while (i+j < 2*N+1) {
        fout << (rk[pw][i] < rk[pw][j] ? conc[i++] : conc[j++]);
        if ((i+j-(N+1)) % 80 == 0) fout << "\n";
    }
    if ((i+j-(N+1)) % 80 != 0) fout << "\n";

    return 0;
}