最好的牛线，金
| 时间限制： 5000MS | 内存限制： 65536K | |
| 提交总数： 5917 | 接受： 2048 |
描述
FJ即将把他的?（1≤ ? ≤30,000）头牛竞争一年一度的“年度农民”。在这个比赛中，每个农民都把他的牛排成一行，并把他们放在法官面前。
比赛组织者今年通过了一个新的注册方案：只要按照他们将要出现的顺序（即，如果FJ依次注册贝西，西尔维娅和多拉，他只注册BSD）登记每头牛的首字母。注册阶段结束后，按照奶牛姓名首字母的字符串，按增加的字典顺序对每个组进行判断。
FJ今年很忙，不得不赶回农场，所以他想尽早做出判断。他决定重新排列已经列队的牛，然后登记它们。
FJ标志着一个新的竞争奶牛的位置。然后，他通过反复将原始行（剩余部分）中的第一头或最后一头母牛发送到新行的末尾，将母牛从旧行进行编组到新行。当他完成之后，FJ就以这个新的顺序把他的奶牛注册了。
鉴于他的牛的初始秩序，确定他可以这样做的最小的字典串首字母缩写。
输入
*第1行：单个整数：N
*行2 .. N +1：第i + 1行包含原始行中第i个位置的牛的单个初始（'A'..'Z'）
产量
他能做的最少的字典串。每一行（可能除了最后一行）都包含新行的80头母牛（'A'..'Z'）的首字母缩写。
示例输入
6 一个 C d 乙 C 乙
示例输出
ABCBCD
题意：每次从字符串首或尾拿出一个字符，求最小字典序方案
拿出字符字典序最小
①我们比较首尾，如果不同，肯定选最小那个
②如果相同，我们比较它的下一位，以此类推
由此，我们可以看出，其实左边的就是后缀，右边的就是将字符串反过来的后缀，二者进行比较
这就很简单了，我们将字符串翻转接到原字符串后边，用一个#之类的隔开，求一次后缀数组用rank贪心加入答案即可
【80个换一次行是什么蛇皮输出= =，没看到一直PE】
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long int
#define REP(i,n) for (int i = 1; i <= (n); i++)
#define REP0(i,n) for (int i = 0; i <= (n); i++)
#define PRE(i,n) for (int i = n; i >= 1; i--)
#define Redge(u) for (int k = head[u]; k != -1; k = edge[k].next)
using namespace std;
const int maxn = 60005,maxm = 100005,INF = 1000000000;
char s[maxn],ans[maxn];
int sa[maxn],rank[maxn],n,m,N,t1[maxn],t2[maxn],c[maxn];
void SA(){int *x = t1,*y = t2;REP0(i,m) c[i] = 0;REP(i,n) c[x[i] = s[i]]++;REP(i,m) c[i] += c[i - 1];PRE(i,n) sa[c[x[i]]--] = i;for (int k = 1; k <= n; k <<= 1){int p = 0;for (int i = n - k + 1; i <= n; i++) y[++p] = i;REP(i,n) if (sa[i] - k > 0) y[++p] = sa[i] - k;REP0(i,m) c[i] = 0;REP(i,n) c[x[y[i]]]++;REP(i,m) c[i] += c[i - 1];PRE(i,n) sa[c[x[y[i]]]--] = y[i];swap(x,y);x[sa[1]] = p = 1;for (int i = 2; i <= n; i++)x[sa[i]] = y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k] ? p : ++p;if (p >= n) break;m = p;}REP(i,n) rank[sa[i]] = i;
}
int main(){cin>>N; m = 256; n = (N << 1) + 1;REP(i,N){s[i] = getchar();while (!isalpha(s[i])) s[i] = getchar();s[n + 1 - i] = s[i];}s[N + 1] = '#';SA();int L = 1,R = N,ansi = 0,r1,r2;while (L < R){r1 = rank[L]; r2 = rank[n + 1 - R];ans[++ansi] = r1 < r2 ? s[L++] : s[R--];}ans[++ansi] = s[L];REP(i,ansi){putchar(ans[i]);if (i % 80 == 0) puts("");}return 0;
}