Description
喜欢钻研问题的JS同学，最近又迷上了对加密方法的思考。一天，他突然想出了一种他认为是终极的加密办法：把需要加密的信息排成一圈，显然，它们有很多种不同的读法。例如下图，可以读作：
JSOI07 SOI07J OI07JS I07JSO 07JSOI 7JSOI0把它们按照字符串的大小排序：07JSOI 7JSOI0 I07JSO JSOI07 OI07JS SOI07J读出最后一列字符：I0O7SJ，就是加密后的字符串（其实这个加密手段实在很容易破解，鉴于这是突然想出来的，那就^^）。但是，如果想加密的字符串实在太长，你能写一个程序完成这个任务吗？
Input
输入文件包含一行，欲加密的字符串。注意字符串的内容不一定是字母、数字，也可以是符号等。
Output
输出一行，为加密后的字符串。
Sample Input
JSOI07
Sample Output
I0O7SJ
HINT
对于100%的数据字符串的长度不超过100000。
题解
两年啦的坑填上了今天，认真学了后缀数组
环的问题嘛，那就再接一段排在后面咯，只用接到len-1就够啦因为len位只用到len+len-1位
接了之后跑一遍SA，然后判一下开头在不在原串里面，输出结尾就好
挺裸的SA的，连height都没用。。
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
using namespace std;
int Rank[210000],Rsort[210000],sa1[210000],sa2[210000];
int tt[210000],a[210000];
char s[210000];
void get_sa(int len,int m)
{memcpy(Rank,a,sizeof(Rank));memset(Rsort,0,sizeof(Rsort));for(int i=1;i<=len;i++)Rsort[Rank[i]]++;for(int i=1;i<=m;i++)Rsort[i]+=Rsort[i-1];for(int i=len;i>=1;i--)sa1[Rsort[Rank[i]]--]=i;int ln=1,p=0;while(p<len){int k=0;for(int i=len-ln+1;i<=len;i++)sa2[++k]=i;for(int i=1;i<=len;i++)if(sa1[i]-ln>0)sa2[++k]=sa1[i]-ln;memset(Rsort,0,sizeof(Rsort));for(int i=1;i<=len;i++)Rsort[Rank[i]]++;for(int i=1;i<=m;i++)Rsort[i]+=Rsort[i-1];for(int i=len;i>=1;i--)sa1[Rsort[Rank[sa2[i]]]--]=sa2[i];memcpy(tt,Rank,sizeof(tt));Rank[sa1[1]]=1;p=1;for(int i=2;i<=len;i++){if(tt[sa1[i]]!=tt[sa1[i-1]] || tt[sa1[i]+ln]!=tt[sa1[i-1]+ln])p++;Rank[sa1[i]]=p;}ln*=2;m=p;}
}
/*
int height[210000];
void get_he(int len)
{int j,k=0;for(int i=2;i<=len;i++){j=sa1[Rank[i]-1];if(k!=0)k--;while(a[i+k]==a[j+k])k++;height[Rank[i]]=k;}
}*/
int main()
{scanf("%s",s+1);int len=strlen(s+1);int q=len;for(int i=1;i<len;i++)s[i+len]=s[i];len*=2;len--;for(int i=1;i<=len;i++)a[i]=s[i];get_sa(len,300);for(int i=1;i<=len;i++){if(sa1[i]<=q)printf("%c",s[sa1[i]+q-1]);}return 0;
}