BZOJ_1031_[JSOI2007]字符加密Cipher_后缀数组
输入文件包含一行，欲加密的字符串。注意字符串的内容不一定是字母、数字，也可以是符号等。
输出一行，为加密后的字符串。
对于100%的数据字符串的长度不超过100000。
学习一下后缀数组。
感觉倍增的思路还是能理解的，就是把长度为$2^{i-1}$的两段存成两个关键字然后基数排序嘛。
代码非常不友好，不过好在大家用的代码基本都差不多。
然后这道题的话把环倍长成链，按照sa数组输出最后一个字符即可。
代码：
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define N 200050
int ws[N],wa[N],wb[N],wv[N],r[N],n,m=129,rank[N],height[N],sa[N];
char str[N];
void build_suffix_array() {
int i,j,p,*x=wa,*y=wb,*t;
for(i=0;i<m;i++) ws[i]=0;
for(i=0;i<n;i++) ws[x[i]=r[i]]++;
for(i=1;i<m;i++) ws[i]+=ws[i-1];
for(i=n-1;i>=0;i--) sa[--ws[x[i]]]=i;
for(j=p=1;p<n;j<<=1,m=p) {
for(p=0,i=n-j;i<n;i++) y[p++]=i;
for(i=0;i<n;i++) if(sa[i]-j>=0) y[p++]=sa[i]-j;
for(i=0;i<n;i++) wv[i]=x[y[i]];
for(i=0;i<m;i++) ws[i]=0;
for(i=0;i<n;i++) ws[wv[i]]++;
for(i=1;i<m;i++) ws[i]+=ws[i-1];
for(i=n-1;i>=0;i--) sa[--ws[wv[i]]]=y[i];
for(t=x,x=y,y=t,x[sa[0]]=0,p=i=1;i<n;i++) {
if(y[sa[i-1]]==y[sa[i]]&&y[sa[i-1]+j]==y[sa[i]+j]) x[sa[i]]=p-1;
else x[sa[i]]=p++;
}
}
/*for(i=1;i<n;i++) rank[sa[i]]=i;
for(i=p=0;i<n-1;height[rank[i++]]=p)
for(p?p--:0,j=sa[rank[i]-1];r[i+p]==r[j+p];p++); */
}
int main() {
scanf("%s",str);
int len=strlen(str);
int i;
for(i=0;i<len;i++) str[i+len]=str[i];
for(i=0;i<len<<1;i++) r[i]=str[i];
r[len<<1]=0;
n=(len<<1)+1;
build_suffix_array();
for(i=0;i<n;i++) {
if(sa[i]<len) printf("%c",str[sa[i]+len-1]);
}
}
BZOJ_1031_[JSOI2007]字符加密Cipher_后缀数组
原文：https://www.cnblogs.com/suika/p/8968140.html