bzoj 1031: [JSOI2007]字符加密Cipher-白红宇

bzoj 1031: [JSOI2007]字符加密Cipher

阅读量：4504 次

发布时间：2019-06-08

本文共 1080 字，大约阅读时间需要 3 分钟。

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

真正的后缀数组板子题，仅次于后缀排序。。。没啥好说的。。。

// MADE BY QT666#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;typedef long long ll;const int N=200050;int gi(){  int x=0,flag=1;  char ch=getchar();  while(ch<'0'||ch>'9'){if(ch=='-') flag=-1;ch=getchar();}  while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();  return x*flag;}int sa[N*2],y[N*2],len,rk;char ch[N*2],a[N*2];struct data{  int x1,x2,id;}x[N];bool cmp(const data &a,const data &b){  if(a.x1==b.x1) return a.x2