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

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

裸的后缀数组，一开始想的是后缀自动机（囧，建好自动机后按字典序dfs遍历长度为len的，直接超时和爆内存）

const
    maxn=200010;
var
    sa,x,y,c:array[0..maxn]of longint;
    s:ansistring;
    n:longint;

procedure init;
var
    i,k:longint;
begin
    readln(s);
    s:=s+s;
    n:=length(s);
    for i:=1 to n do
      begin
        y[i]:=ord(s[i]);
        x[i]:=y[i];
      end;
    for i:=1 to n do
      inc(c[y[i]]);
    for i:=2 to 128 do
      inc(c[i],c[i-1]);
    for i:=1 to n do
      begin
        sa[c[y[i]]]:=i;
        dec(c[y[i]]);
      end;
    x[sa[1]]:=1;
    k:=1;
    for i:=2 to n do
      begin
        if y[sa[i]]<>y[sa[i-1]] then inc(k);
        x[sa[i]]:=k;
      end;
end;

procedure work;
var
    p,i,k:longint;
begin
    p:=1;
    while p<n do
      begin
        for i:=1 to n-p do
          y[i]:=x[i+p];
        for i:=n-p+1 to n do
          y[i]:=0;
        for i:=0 to n do
          c[i]:=0;
        for i:=1 to n do
          inc(c[y[i]]);
        for i:=1 to n do
          inc(c[i],c[i-1]);
        for i:=1 to n do
          begin
            sa[c[y[i]]]:=i;
            dec(c[y[i]]);
          end;
        for i:=0 to n do
          c[i]:=0;
        for i:=1 to n do
          inc(c[x[i]]);
        for i:=1 to n do
          inc(c[i],c[i-1]);
        for i:=n downto 1 do
          begin
            y[sa[i]]:=c[x[sa[i]]];
            dec(c[x[sa[i]]]);
          end;
        for i:=1 to n do
          sa[y[i]]:=i;
        y[sa[1]]:=1;
        k:=1;
        for i:=2 to n do
          begin
            if (x[sa[i]]<>x[sa[i-1]]) or (x[sa[i]+p]<>x[sa[i-1]+p]) then inc(k);
            y[sa[i]]:=k;
          end;
        x:=y;
        p:=p<<1;
      end;
    for i:=1 to n do
      sa[x[i]]:=i;
    for i:=1 to n do
      if sa[i]<=n>>1 then write(s[sa[i]+n>>1-1]);
end;

begin
    init;
    work;
end.