题目描述：
喜欢钻研问题的JS 同学，最近又迷上了对加密方法的思考。一天，他突然想出了一种他认为是终极的加密办法：把需要加密的信息排成一圈，显然，它们有很多种不同的读法。
例如‘JSOI07’，可以读作： JSOI07 SOI07J OI07JS I07JSO 07JSOI 7JSOI0 把它们按照字符串的大小排序： 07JSOI 7JSOI0 I07JSO JSOI07 OI07JS SOI07J 读出最后一列字符：I0O7SJ，就是加密后的字符串（其实这个加密手段实在很容易破解，鉴于这是突然想出来的，那就^^）。 但是，如果想加密的字符串实在太长，你能写一个程序完成这个任务吗？
题解：
其实就是后缀数组裸题。
倍长后求sa数组，然后扫一遍输出就好了。
代码：
#include<cstdio>#include<cstring>#include<algorithm>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;}[JSOI2007]字符加密
原文地址：https://www.cnblogs.com/LiGuanlin1124/p/10011083.html