BZOJ-1031: [JSOI2007]字符加密Cipher

Description

把需要加密的信息排成一圈，显然，它们有很多种不同的读法。例如下图，可以读作：

JSOI07 SOI07J OI07JS I07JSO 07JSOI 7JSOI0把它们按照字符串的大小排序：07JSOI 7JSOI0 I07JSO JSOI07
OI07JS SOI07J读出最后一列字符：I0O7SJ，就是加密后的字符串。但是，如果想加密的字符串实在太长，你能写一个程序完成这个任务吗？字符串的长度不超过100000。

后缀数组裸题。（11个循环的板子也是感动死我了）

遇到环的问题要么差环，要么倍增。--CQzhangyu

所以将字符串倍增，求sa数组，将在后半部分的剔除。

#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 201000 
using namespace std;
int n,m;
int sa[N],r[N];
char str[N];
void suffix_array(int len,int lp)
{
    int i,j,k;
    static int x[N<<1],y[N<<1],ws[N];
    memset(ws,0,sizeof(int)*lp);
    for(i=0;i<len;++i) ws[x[i]=r[i]]++;
    for(i=1;i<lp;++i) ws[i]+=ws[i-1];
    for(i=len-1;i>=0;--i) sa[--ws[x[i]]]=i;
    for(j=k=1;k<len;j<<=1,lp=k)
    {
        for(k=0,i=len-j;i<len;++i) y[k++]=i;
        for(i=0;i<len;++i) if(sa[i]>=j) y[k++]=sa[i]-j;
        memset(ws,0,sizeof(int)*lp);
        for(i=0;i<len;++i) ws[x[i]]++;
        for(i=1;i<lp;++i) ws[i]+=ws[i-1];
        for(i=len-1;i>=0;--i) sa[--ws[x[y[i]]]]=y[i];
        for(swap(x,y),i=k=1,x[sa[0]]=0;i<len;++i)
            x[sa[i]]=(y[sa[i-1]]==y[sa[i]]&&y[sa[i-1]+j]==y[sa[i]+j])?k-1:k++;
    }
}
int main()
{
    scanf("%s",str); n=strlen(str); int i;
    for(i=0;i!=n;++i) r[i]=r[i+n]=str[i],m=max(m,r[i]);
    m++; n<<=1; r[n++]=0; suffix_array(n,m);
    for(i=0;i!=n;++i)
        if(sa[i]<n/2) printf("%c",str[(sa[i]+n/2-1)%(n/2)]);
    return 0;
}