bzoj 1031: [JSOI2007]字符加密Cipher

.

裸后缀数组
因为学了好几次倍增都没学懂，所以这次决定学DC3！经过将近两天的研究，我发现还是Juha Kärkkäinen and Peter Sanders的论文里的代码好懂比罗穗骞的代码不知道高到哪里去了
代码：
垃圾bzoj不支持tuple，CE了两发

#include<bits/stdc++.h>
using namespace std;

char ss[200010];
int s[200010],sa[200010];

#ifdef ONLINE_JUDGE
pair<pair<int,int>,int> make_tuple(const int &x,const int &y,const int &z)
{
    return make_pair(make_pair(x,y),z);
}
#endif
inline int g(int x,int n0)
{
    return x<n0?x*3+1:(x-n0)*3+2;
}
void radix(int *a,int *b,int *s,int n,int K)
{
    int *hh=new int[K+1];
    for(int i=0;i<=K;i++)
    hh[i]=0;
    for(int i=0;i<n;i++)
    hh[s[a[i]]]++;
    for(int i=1;i<=K;i++)
    hh[i]+=hh[i-1];
    for(int i=n-1;i>=0;i--)
    b[--hh[s[a[i]]]]=a[i];
}
void dc3(int *s,int *sa,int n,int K)
{
    int n0=(n+2)/3,n1=(n+1)/3,n2=n/3,n02=n0+n2;
    int *s12=new int[n02+3];
    s12[n02]=s12[n02+1]=s12[n02+2]=0;
    int *sa12=new int[n02+3];
    sa12[n02]=sa12[n02+1]=sa12[n02+2]=0;
    int *s0=new int[n0];
    int *sa0=new int[n0];
    for(int i=0,hh=0;i<n;i++)
    if(i%3)
    s12[hh++]=i;
    if(n%3==1)
    s12[n02-1]=n;
    radix(s12,sa12,s+2,n02,K);
    radix(sa12,s12,s+1,n02,K);
    radix(s12,sa12,s,n02,K);
    int name=0,c1=-1,c2=-1,c3=-1;
    for(int i=0;i<n02;i++)
    {
        if(s[sa12[i]]!=c1||s[sa12[i]+1]!=c2||s[sa12[i]+2]!=c3)
        {
            c1=s[sa12[i]];
            c2=s[sa12[i]+1];
            c3=s[sa12[i]+2];
            name++;
        }
        if(sa12[i]%3==1)
        s12[sa12[i]/3]=name;
        else
        s12[sa12[i]/3+n0]=name;
    }
    if(name<n02)
    {
        s12[n02]=s12[n02+1]=s12[n02+2]=0;
        dc3(s12,sa12,n02,name);
        for(int i=0;i<n02;i++)
        s12[sa12[i]]=i+1;
    }
    else
    {
        for(int i=0;i<n02;i++)
        sa12[s12[i]-1]=i;
    }
    for(int i=0,hh=0;i<n02;i++)
    {
        if(sa12[i]<n0)
        s0[hh++]=sa12[i]*3;
    }
    radix(s0,sa0,s,n0,K);
    int i=n0-n1,j=0,hh=0;
    while(i<n02&&j<n0)
    {
        if(sa12[i]<n0&&make_pair(s[g(sa12[i],n0)],s12[sa12[i]+n0])<make_pair(s[sa0[j]],s12[sa0[j]/3])||
        sa12[i]>=n0&&make_tuple(s[g(sa12[i],n0)],s[g(sa12[i],n0)+1],s12[sa12[i]+1-n0])<make_tuple(s[sa0[j]],s[sa0[j]+1],s12[sa0[j]/3+n0]))
        sa[hh++]=g(sa12[i++],n0);
        else
        sa[hh++]=sa0[j++];
    }
    while(i<n02)
    sa[hh++]=g(sa12[i++],n0);
    while(j<n0)
    sa[hh++]=sa0[j++];
    delete[] s12;
    delete[] sa12;
    delete[] s0;
    delete[] sa0;
}
int main()
{
    scanf("%s",ss);
    int len=strlen(ss);
    for(int i=0;i<len;i++)
    s[i]=ss[i];
    for(int i=0;i<len;i++)
    s[i+len]=ss[i];
    len<<=1;
    s[len]=s[len+1]=s[len+2]=0;
    dc3(s,sa,len,127);/*
    for(int i=0;i<len;i++)
    printf("%d\n",sa[i]);*/
    for(int i=0;i<len;i++)
    {
        if(sa[i]<(len>>1))
        printf("%c",s[sa[i]-1+(len>>1)]);
    }
}