Description

　喜欢钻研问题的JS同学，最近又迷上了对加密方法的思考。一天，他突然想出了一种他认为是终极的加密办法
：把需要加密的信息排成一圈，显然，它们有很多种不同的读法。例如下图，可以读作：
这里写图片描述

JSOI07 SOI07J OI07JS I07JSO 07JSOI 7JSOI0把它们按照字符串的大小排序：07JSOI 7JSOI0 I07JSO JSOI07
OI07JS SOI07J读出最后一列字符：I0O7SJ，就是加密后的字符串（其实这个加密手段实在很容易破解，鉴于这是
突然想出来的，那就^^）。但是，如果想加密的字符串实在太长，你能写一个程序完成这个任务吗？

对于100%的数据字符串的长度不超过100000。

Solution

本蒟蒻的第一题后缀数组SA，纪念一下
把原串复制一份加在后面，跑出来的所有后缀中长度>=len的按顺序排序，每个取最后一位就ok
膜来的板子a啊b啊c啊d啊乱七八糟的有点晕，但是想不到更好的替代
辣鸡csdn，卡屎了

Code

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<vector>
#define rep(i,st,ed)for(int i=st;i<=ed;++i)
#define drp(i,st,ed)for(int i=st;i>=ed;--i)
#define fill(x,t) memset(x,t,sizeof(x))
#define copy(x,t) memcpy(x,t,sizeof(x))

constint N=200005;

int rank[N],sa[N],h[N];
int b[N],c[N],d[N];

char s[N],ans[N];

void get_sa(int n,int m){
    rep(i,0,m) b[i]=0;
    rep(i,1,n) b[s[i]]++;
    rep(i,1,m) b[i]+=b[i-1];
    drp(i,n,1) c[b[s[i]]--]=i;
int t=0;
    rep(i,1,n){
if(s[c[i]]!=s[c[i-1]]) t++;
        rank[c[i]]=t;
}
int j=1;
while(j<=n){
        rep(i,0,n) b[i]=0;
        rep(i,1,n) b[rank[i+j]]++;
        rep(i,1,n) b[i]+=b[i-1];
        drp(i,n,1) c[b[rank[i+j]]--]=i;
        rep(i,0,n) b[i]=0;
        rep(i,1,n) b[rank[i]]++;
        rep(i,1,n) b[i]+=b[i-1];
        drp(i,n,1) d[b[rank[c[i]]]--]=c[i];
int t=0;
        rep(i,1,n){
if(rank[d[i]]!=rank[d[i-1]]||rank[d[i]]==rank[d[i-1]]&&rank[d[i]+j]!=rank[d[i-1]+j]) t++;
            c[d[i]]=t;
}
        rep(i,1,n) rank[i]=c[i];
if(t==n)break;
        j*=2;
}
    rep(i,1,n)
        sa[rank[i]]=i;
}

void get_height(int n){
int k=0;
    rep(i,1,n){
if(k) k--;
int j=sa[rank[i]-1];
while(i+k<=n&&j+k<=n&&s[i+k]==s[j+k]) k++;
        h[rank[i]]=k;
}
}

int main(void){
scanf("%s", s);int len=strlen(s),m=0;
    drp(i,len,1){
        s[i+len]=s[i]=s[i-1];
        m=std:: max(m,(int)s[i]);
}
    get_sa(len*2,m);
    get_height(len*2);
int j=0;
    rep(i,1,len*2)if(sa[i]<=len) ans[++j]=s[sa[i]+len-1];
    rep(i,1,len)printf("%c",ans[i]);
return0;
}