1031: [JSOI2007]字符加密Cipher
Time Limit: 10 Sec Memory Limit: 162 MBSubmit: 7756 Solved: 3365
[Submit][Status][Discuss]
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。
/* ???把字符串复制一遍，就是后缀数组裸题了，函数calsa里有几个细节还没看懂 */ #include<iostream>#include<cstdio>#include<cstring>#define maxn 200010using namespace std;char ch[maxn];int a[maxn],n,k;int v[maxn],sa[2][maxn],rank[2][maxn];void calsa(int sa[maxn],int rank[maxn],int SA[maxn],int Rank[maxn]){ ???for(int i=1;i<=n;i++)v[rank[sa[i]]]=i;//不明白 ???for(int i=n;i>=1;i--) ???????if(sa[i]>k)SA[v[rank[sa[i]-k]]--]=sa[i]-k; ???for(int i=n-k+1;i<=n;i++) ???????SA[v[rank[i]]--]=i; ???for(int i=1;i<=n;i++) ???????Rank[SA[i]]=Rank[SA[i-1]]+(rank[SA[i-1]]!=rank[SA[i]]||rank[SA[i-1]+k]!=rank[SA[i]+k]);}void work(){ ???int p=0,q=1; ???for(int i=1;i<=n;i++)v[a[i]]++;//v[i]是字符i出现的次数 ????for(int i=1;i<=256;i++)v[i]+=v[i-1]; ???for(int i=1;i<=n;i++)sa[p][v[a[i]]--]=i; ???for(int i=1;i<=n;i++) ???????rank[p][sa[p][i]]=rank[p][sa[p][i-1]]+(a[sa[p][i]]!=a[sa[p][i-1]]);//处理名次重复字符串 ????????k=1; ???while(k<n){//和后缀数组模板的效果是一样的 ????????calsa(sa[p],rank[p],sa[q],rank[q]); ???????p^=1;q^=1;k<<=1; ???} ????for(int i=1;i<=n;i++){ ???????if(sa[p][i]<=n/2) ???????????printf("%c",ch[sa[p][i]+n/2-1]); ???}}int main(){ ???scanf("%s",ch+1); ???n=strlen(ch+1); ???for(int i=1;i<=n;i++){//将字符串复制一遍 ????????a[i]=ch[i]; ???????a[i+n]=a[i]; ???????ch[i+n]=ch[i]; ???} ???n<<=1;work(); ???return 0;}bzoj 1031: [JSOI2007]字符加密Cipher
原文地址：https://www.cnblogs.com/thmyl/p/8110476.html