传送门：

题意：

给出一个长度为N的字符串，每次可以从串头或串尾取一个字符，添加到新串中，使新串的字典序最小。

做法：

经过推导（略），发现只要贪心地取两端字典序较小的一端，所以在一开始对所有的正反后缀排序，即把原串倒过来接在后面求一遍SA就行了。

写了个倍增求SA[]+height[]的板子，代码可能比较长，但相对来说可能容易理解一点...

#include 
    
     #define TR(x) cout<<#x<<'='<
     
      <
      
       =0; --i) sa[--c[x[y[i]]]]=y[i];}inline int cmp(int *x, int a, int b, int k){return x[a]==x[b]&&x[a+k]==x[b+k];}void getsa(){    int *x=ht, *y=rk, up=30;    for(int i=0; i
       
        =k) y[p++]=sa[i]-k;        rsort(x,y,up); swap(x,y); p=1; x[sa[0]]=0;        for(int i=1; i