题目描述：

喜欢钻研问题的JS 同学，最近又迷上了对加密方法的思考。一天，他突然想出了一种他认为是终极的加密办法：把需要加密的信息排成一圈，显然，它们有很多种不同的读法。

例如‘JSOI07’，可以读作： JSOI07 SOI07J OI07JS I07JSO 07JSOI 7JSOI0 把它们按照字符串的大小排序： 07JSOI 7JSOI0 I07JSO JSOI07 OI07JS SOI07J 读出最后一列字符：I0O7SJ，就是加密后的字符串（其实这个加密手段实在很容易破解，鉴于这是突然想出来的，那就^^）。 但是，如果想加密的字符串实在太长，你能写一个程序完成这个任务吗？

题解：

其实就是后缀数组裸题。

倍长后求sa数组，然后扫一遍输出就好了。

代码：

#include
     
      #include
      
       #include
       
        using namespace std;#define N 100050char a[N<<1];int n,sa[N<<1],rank[N<<1],hs[N<<1],tmp[N<<1],s[N<<1];bool cmp(int i,int j,int k){    if(i+k>n||j+k>n)return 0;    return rank[i]==rank[j]&&rank[i+k]==rank[j+k];}void get_sa(){    int i,cnt=0;    for(i=1;i<=n;i++)s[i]=a[i];    for(i=1;i<=n;i++)hs[s[i]]++;    for(i=1;i<=200;i++)if(hs[i])tmp[i]=++cnt;    for(i=1;i<=200;i++)hs[i]+=hs[i-1];    for(i=1;i<=n;i++)rank[i]=tmp[s[i]],sa[hs[s[i]]--]=i;    for(int k=1;cnt!=n;k<<=1)    {        for(i=1;i<=n;i++)hs[i]=0;        for(i=1;i<=n;i++)hs[rank[i]]++;        for(i=1;i<=n;i++)hs[i]+=hs[i-1];        for(i=n;i>=1;i--)if(sa[i]>k)tmp[sa[i]-k]=hs[rank[sa[i]-k]]--;        for(i=1;i<=k;i++)tmp[n-i+1]=hs[rank[n-i+1]]--;        for(i=1;i<=n;i++)sa[tmp[i]]=i;        for(i=1,cnt=0;i<=n;i++)tmp[sa[i]]=cmp(sa[i],sa[i-1],k)?cnt:++cnt;        for(i=1;i<=n;i++)rank[i]=tmp[i];    }}int main(){    scanf("%s",a+1);    n = strlen(a+1);    for(int i=n+1;i<=n*2;i++)a[i]=a[i-n];    n<<=1;    get_sa();    for(int i=1;i<=n;i++)    {        if(sa[i]<=(n/2))            printf("%c",a[sa[i]+(n/2)-1]);    }    printf("\n");    return 0;}