1692: [Usaco2007 Dec]隊列變換
Description
FJ打算帶他的N(1 <= N <= 30,000)頭奶牛去參加一年一度的“全美農場主大獎賽”。在這場比賽中，每個參賽者都必須讓他的奶牛排成一列，然後領她們從裁判席前依次走過。 今年，競賽委員會在接受隊伍報名時，采用了一種新的登記規則：他們把所有隊伍中奶牛名字的首字母取出，按它們對應奶牛在隊伍中的次序排成一列（比如說，如果FJ帶去的奶牛依次為Bessie、Sylvia、Dora，登記人員就把這支隊伍登記為BSD）。登記結束後，組委會將所有隊伍的登記名稱按字典序升序排列，就得到了他們的出場順序。 FJ最近有一大堆事情，因此他不打算在這個比賽上浪費過多的時間，也就是說，他想盡可能早地出場。於是，他打算把奶牛們預先設計好的隊型重新調整一下。 FJ的調整方法是這樣的：每次，他在原來隊列的首端或是尾端牽出一頭奶牛，把她安排到新隊列的尾部，然後對剩余的奶牛隊列重復以上的操作，直到所有奶牛都被插到了新的隊列裡。這樣得到的隊列，就是FJ拉去登記的最終的奶牛隊列。 接下來的事情就交給你了：對於給定的奶牛們的初始位置，計算出按照FJ的調整規則所可能得到的字典序最小的隊列。
Input
* 第1行: 一個整數：N
* 第2..N+1行: 第i+1行僅有1個'A'..'Z'中的字母，表示隊列中從前往後數第i 頭奶牛名字的首字母
Output
* 第1..??行: 輸出FJ所能得到的字典序最小的隊列。每行（除了最後一行）輸 出恰好80個'A'..'Z'中的字母，表示新隊列中每頭奶牛姓名的首 字母
Sample Input
6
A
C
D
B
C
B
輸入說明:
FJ有6頭順次排好隊的奶牛：ACDBCB
Sample Output
ABCBCD
輸出說明:
操作數 原隊列 新隊列
#1 ACDBCB
#2 CDBCB A
#3 CDBC AB
#4 CDB ABC
#5 CD ABCB
#6 D ABCBC
#7 ABCBCD
HINT
Source
Gold
做的第一道後綴數組題，小小地慶祝一下！
選擇原理很簡單，只要比較正序和逆序的字典序即可，然後貪心就可以了。
字典序的比較可以在字符串加一個0，再將整個字符串對稱復制一遍，用後綴數組預處理，每次就可以O(1)比較字典序了。
這道題將字符串對稱復制的思路很好。
#include
#include
#include
#include
#include
#include
#include
#define F(i,j,n) for(int i=j;i<=n;i++)
#define D(i,j,n) for(int i=j;i>=n;i--)
#define ll long long
#define pa pair
#define maxn 60100
#define inf 1000000000
using namespace std;
int a[maxn],x[maxn],y[maxn],c[maxn],sa[maxn],rank[maxn];
int n,l,r,tot,cnt=0;
char ch;
inline void build_sa(int n,int m)
{
memset(c,0,sizeof(c));
F(i,0,n-1) c[x[i]=a[i]]++;
F(i,1,m-1) c[i]+=c[i-1];
D(i,n-1,0) sa[--c[x[i]]]=i;//初始化
for(int k=1;k<=n;k<<=1)
{
int p=0;
F(i,n-k,n-1) y[p++]=i;
F(i,0,n-1) if (sa[i]>=k) y[p++]=sa[i]-k;//根據第二關鍵字排序
memset(c,0,sizeof(c));
F(i,0,n-1) c[x[y[i]]]++;
F(i,1,m-1) c[i]+=c[i-1];
D(i,n-1,0) sa[--c[x[y[i]]]]=y[i];//根據第一關鍵字排序
swap(x,y);
p=1;x[sa[0]]=0;
F(i,1,n-1) x[sa[i]]=y[sa[i-1]]==y[sa[i]]&&y[sa[i-1]+k]==y[sa[i]+k]?p-1:p++;
if (p>=n) break;
m=p;
}
}
int main()
{
scanf("%d",&n);
tot=2*n+1;
F(i,0,n-1)
{
ch=getchar();
while (ch<'A'||ch>'Z') ch=getchar();
a[i]=ch-'A'+1;
}
a[n]=0;a[tot]=0;
F(i,1,n) a[n+i]=a[n-i];
build_sa(tot,27);
F(i,0,tot-1) rank[sa[i]]=i;
l=0;r=n-1;
while (l<=r)
{
if (rank[l]
