题意：
喜欢钻研问题的JS同学，最近又迷上了对加密方法的思考。一天，他突然想出了一种他认为是终极的加密办法
：把需要加密的信息排成一圈，显然，它们有很多种不同的读法。例如下图，可以读作：
JSOI07 SOI07J OI07JS I07JSO 07JSOI 7JSOI0
把它们按照字符串的大小排序：07JSOI 7JSOI0 I07JSO JSOI07 OI07JS SOI07J
读出最后一列字符：I0O7SJ，就是加密后的字符串
（其实这个加密手段实在很容易破解，鉴于这是突然想出来的，那就^^）。
但是，如果想加密的字符串实在太长，你能写一个程序完成这个任务吗？
数据范围：字符串长度<=1e5
解法：
这道题实际上是在环上对每个点作为起点的串进行排序,
序列和环容易想到破环成链,具体做法就是复制一遍序列接在后面.
题目中的每个串一定都是新串的某个后缀的前缀
题目中的n个串就是新串中串[1,n]的后缀的长度为n的前缀
对新串构造后缀数组,sa[1]到sa[n]就是题目的排序结果
那么s[sa[i]+n-1]就是末尾字符
ps：
这种方法似乎可以用来求字符串的最小表示法（第k小表示法？）
code：
#include<bits/stdc++.h>
using namespace std;
const int maxm=1e5+5;
struct SA{static const int N=1e6+5;char s[N];int sa[N],rk[N],oldrk[N<<1],id[N],px[N],cnt[N];int n;bool cmp(int x,int y,int w){return oldrk[x]==oldrk[y]&&oldrk[x+w]==oldrk[y+w];}void getSA(){int m=300;//字符集大小int i,p,w;for(i=1;i<=n;i++)cnt[rk[i]=s[i]]++;for(i=1;i<=m;i++)cnt[i]+=cnt[i-1];for(i=n;i>=1;i--)sa[cnt[rk[i]]--]=i;//for(w=1;w<n;w<<=1,m=p){for(p=0,i=n;i>n-w;i--)id[++p]=i;for(i=1;i<=n;i++)if(sa[i]>w)id[++p]=sa[i]-w;memset(cnt,0,sizeof cnt);for(i=1;i<=n;i++)cnt[px[i]=rk[id[i]]]++;for(i=1;i<=m;i++)cnt[i]+=cnt[i-1];for(i=n;i>=1;i--)sa[cnt[px[i]]--]=id[i];memcpy(oldrk,rk,sizeof rk);for(p=0,i=1;i<=n;i++){rk[sa[i]]=cmp(sa[i],sa[i-1],w)?p:++p;}}//
// for(int i=1;i<=n;i++)printf("%d ",sa[i]);
// puts("");}
}sa;
signed main(){scanf("%s",sa.s+1);sa.n=strlen(sa.s+1);//复制for(int i=1;i<=sa.n;i++)sa.s[i+sa.n]=sa.s[i];sa.n*=2;//sa.getSA();for(int i=1;i<=sa.n;i++){if(sa.sa[i]<=sa.n/2){printf("%c",sa.s[sa.sa[i]+sa.n/2-1]);}}return 0;
}