「BZOJ1031」[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数据规模
对于40%的数据字符串的长度不超过10000。
对于100%的数据字符串的长度不超过100000。
对于40%的数据字符串的长度不超过10000。
对于100%的数据字符串的长度不超过100000。
题解
有时候你需要一个善良的学长…
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 |
#include<iostream> #include<cstdio> #include<cstring> #define N 200001 using namespace std; char ch[N]; int a[N],n,k; int v[N],sa[2][N],rank[2][N]; void ini() { scanf("%s",ch+1); n=strlen(ch+1); for(int i=1;i<=n;++i) { a[i]=int(ch[i]); a[i+n]=a[i]; ch[i+n]=ch[i]; } n<<=1; } void calsa(int sa[N],int rank[N],int SA[N],int Rank[N]) { 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]]++; 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() { ini(); work(); return 0; } |
计数器 9793916
OI 课件=>
OI 课件=>
就像您一样的善良的学长
OrzSA
未来国家队别d我
orz——都开始虐SA啦（我现在是被SA虐）