BZOJ1031[JSOI2007]字符加密Cipher

1031: [JSOI2007]字符加密Cipher

Time Limit: 10 Sec   Memory Limit: 162 MB Submit: 7402   Solved: 3205 [ 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。

Source

 调了半天没调对气得砸键盘。其实好水啦，把字符串复制一遍做个后缀数组,sa[i]小于n的输出就行了。

  

#include <bits/stdc++.h> using namespace std; #define maxn 200005 int sa[maxn],tp[maxn],tax[maxn],rk[maxn]; int a[maxn]; char s[maxn]; int n; bool cmp(int *f,int i,int k) { return (f[sa[i]]==f[sa[i-1]] && f[sa[i]+k]==f[sa[i-1]+k]); } void build_sa() { int m=256; int p=0; for (int i=0;i<m;i++) tax[i]=0; for (int i=0;i<n;i++) tax[rk[i]=a[i]]++; for (int i=1;i<m;i++)tax[i]+=tax[i-1]; for (int i=n-1;i>=0;i--) sa[--tax[rk[i]]]=i; for (int k=1;k<=n;k<<=1) { int p=0; for (int i=n-k;i<n;i++) tp[p++]=i; for (int i=0;i<n;i++) if (sa[i]>=k) tp[p++]=sa[i]-k; for (int i=0;i<m;i++)tax[i]=0; for (int i=0;i<n;i++)tax[rk[tp[i]]]++; for (int i=1;i<m;i++) tax[i]+=tax[i-1]; for (int i=n-1;i>=0;i--)sa[--tax[rk[tp[i]]]]=tp[i]; p=0; swap(tp,rk); rk[sa[0]]=0; for (int i=1;i<n;i++)rk[sa[i]]=cmp(tp,i,k)?p:++p; if (++p>=n) break; m=p; } } int main() { char ss[maxn]; scanf("%s",s); n = strlen(s); int nn=n; for (int _=0;_<=n-1;_++) s[_+n] = s[_]; n *= 2; n++; for (int i=0;i<n-1;i++) a[i]=s[i]; a[n-1]=0; build_sa(); for (int i=1;i<n;i++)if (sa[i]<nn) cout<<s[sa[i]+nn-1]; cout<<endl; }