poj 3623 字符串翻转后的和原串后的数组进行求后缀数组，然后之后两个指针 i，j 选择两端 rk 值最小的输出，注意格式
#include<cstdio> #include<cstring> #include<algorithm> #include<vector> #define ms(i, j) memset(i, j, sizeof i) #define ll long long using namespace std; const int MAXN = 30000 * 2 + 5; int N, n, m, a[MAXN]; int SA[MAXN], rk[MAXN], tp[MAXN], tax[MAXN]; bool cmp(int *f, int i, int k) {return f[SA[i]]==f[SA[i-1]]&&f[SA[i]+k]==f[SA[i-1]+k];} void build() { for (int i=0;i<m;i++) tax[i] = 0; for (int i=0;i<n;i++) tax[rk[i]=a[i]]++; for (int i=1;i<m;i++) tax[i] += tax[i-1]; for (int i=n-1;i>=0;i--) SA[--tax[rk[i]]] = i; int p; for (int k=1;k<=n;k*=2) { p = 0; for (int i=n-k;i<n;i++) tp[p++] = i; for (int i=0;i<n;i++) if (SA[i]>=k) tp[p++] = SA[i] - k; for (int i=0;i<m;i++) tax[i] = 0; for (int i=0;i<n;i++) tax[rk[tp[i]]]++; for (int i=1;i<m;i++) tax[i] += tax[i-1]; for (int i=n-1;i>=0;i--) SA[--tax[rk[tp[i]]]] = tp[i]; swap(tp, rk), p = 0, rk[SA[0]] = 0; for (int i=1;i<n;i++) rk[SA[i]] = cmp(tp, i, k) ? p : ++p; if (++p>=n) break; m = p; } } void init() { char ch[10]; n = N; for (int i=0;i<N;i++) { scanf("%s", ch); a[i] = ch[0]; } a[n++] = '$'; for (int i=N-1;i>=0;i--) { a[n++] = a[i]; } a[n++] = 0; m = 128; } void solve() { build(); int i = 0, j = N+1, tot = 0; do { if (rk[i]<rk[j]) putchar(a[i]), i++, tot++; else putchar(a[j]), j++, tot++; if (tot%80==0) printf("\n"); } while (tot<N); printf("\n"); } int main() { #ifndef ONLINE_JUDGE freopen("1.in", "r", stdin);freopen("1.out", "w", stdout); #endif while (scanf("%d", &N)==1&&N) init(), solve(); return 0; }