1031: [JSOI2007]字符加密Cipher
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。
这是一道delicious の 后缀数组题
把原字符串复制一遍接到后面，然后。。。后缀数组
#include<cstdio>
#include<cstring>
#include<iostream>
#define MaxN 200010
using namespace std;
int n;
char s[MaxN];
int rank[MaxN];
int height[MaxN];
int sa[MaxN];
int w[MaxN];
void SA(){
int *x=rank;
int *y=height;
int m=256;
for (int i=1;i<=n;++i) ++w[x[i]=s[i]];
for (int i=2;i<=m;++i) w[i]+=w[i-1];
for (int i=1;i<=n;++i) sa[w[x[i]]--]=i;
for (int k=1;k<n;k<<=1,swap(x,y)){
int t=0;
for (int i=n-k+1;i<=n;++i) y[++t]=i;
for (int i=1;i<=n;++i)
if (sa[i]-k>0) y[++t]=sa[i]-k;
memset(w+1,0,sizeof(int)*m);
for (int i=1;i<=n;++i) ++w[x[i]];
for (int i=2;i<=m;++i) w[i]+=w[i-1];
for (int i=n;i;--i) sa[w[x[y[i]]]--]=y[i];
m=0;
for (int i=1;i<=n;++i){
int u=sa[i],v=sa[i-1];
y[u]=i==1||x[u]!=x[v]||x[u+k]!=x[v+k]?++m:m;
}
if (m==n) break;
}
if (rank!=y) memcpy(rank+1,y+1,sizeof(int)*n);
}
int main(){
scanf("%s",s+1);
n=strlen(s+1);
for (int i=1;i<=n;++i)
s[i+n]=s[i];
n+=n;
SA();
for (int i=1;i<=n;++i)
if (sa[i]<=n/2)
printf("%c",s[sa[i]+n/2-1]);
printf("\n");
}
评论 (0)
