想知道这种做法正不正确。

如果正确的话怕不是要吊打hash……

#include <cstdio>
#define uint unsigned int

#define MAXN 500005

inline void Input();
inline void Solve();

int main()
{
    Input(); Solve();
    return 0;
}

uint n;
char s1[MAXN], s2[MAXN];

inline void Input() {
    scanf("%u", &n);
    char ch;
    for(uint i = 1; i <= n; ++i) {
        do ch = getchar(); while(ch < 'A' || ch > 'Z');
        s1[i] = s2[n - i + 1] = ch;
    }
}

uint ptn = 0;
inline void putstr(char *ts, uint l, uint r) {
    while(l <= r && ptn < n) {
        ++ptn;
        putchar(ts[l++]);
        if(ptn % 80 == 0) 
        putchar('\n');
    }
}

inline void Solve() {
    if(n == 1) putchar(s1[1]);
    for(uint p1 = 1, p2 = 1; p1 + p2 < n + 2;) {
        if(s1[p1] != s2[p2]) {
            if(s1[p1] < s2[p2]) putchar(s1[p1++]);
            else putchar(s2[p2++]);
            ++ptn;
            if(ptn % 80 == 0) putchar('\n');
            continue;
        }
        uint lp = 1, tp = 1;
        while(true) {
            uint np1 = p1 + tp, np2 = p2 + tp;
            if(np1 > n) {
                putstr(s1, p1, n);
                p1 = n + 1; break;
            } else if(np2 > n) {
                putstr(s2, p2, n);
                p2 = n + 1; break;
            }
            if(s1[np1] < s1[np1 - lp] || s2[np2] < s1[np1 - lp]) {
                if(s1[np1] == s2[np2]) {
                    ++tp; lp = tp;
                    continue;
                } else if(s1[np1] < s2[np2]) {
                    putstr(s1, p1, np1);
                    p1 = np1 + 1; break;
                } else {
                    putstr(s2, p2, np2);
                    p2 = np2 + 1; break;
                }
            } else if(s1[np1] > s1[np1 - lp] || s2[np2] > s1[np1 - lp]) {
                if(s1[np1] > s1[np1 - lp])
                    putstr(s2, p2, p2 + lp - 1), p2 += lp;
                if(s2[np2] > s1[np1 - lp])
                    putstr(s1, p1, p1 + lp - 1), p1 += lp;
                break;
            } else {
                ++tp;
                if(tp >= lp * 2) lp = tp;
                continue;
            }
        }
    }
    putchar('\n');
}