代码

#include <iostream>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>

using namespace std;

const int MAXBUF=20000005;
char B[MAXBUF],*Si=B,*Ti=B;
inline char getc()
{if (Si==Ti) Ti=(Si=B)+fread(B,1,MAXBUF,stdin);
if (Si==Ti) return 0;
return *Si++;
}
template <class T>
inline void read(T &a)
{static char c;
while ((c=getc())<'0'||c>'9');a=c-'0';
while ((c=getc())>='0'&&c<='9') a=(a<<3)+(a<<1)+c-'0';
}
char Buff[MAXBUF],*sti=Buff;
template <class T>
inline void write(T a)
{if (a==0) {*sti++='0';return;}
int t[21],cnt=0;
while (a) t[++cnt]=a%10,a/=10;
for (int i=cnt;i>=1;i--) *sti++='0'+t[i];
}

const int N=100010;

char s[N];
int n,sa[N],sa2[N<<1],rk[N<<1],px[N],cnt[N],height[N];

bool cmp(int x,int y,int w) { return sa2[x]==sa2[y]&&sa2[x+w]==sa2[y+w]; }

int main()
{
    int i,j,k,w,p,m=300;
    
    scanf("%s",s+1);
    n=strlen(s+1);
    
    for (i=1;i<=n;++i) rk[i]=s[i];
    for (i=1;i<=n;++i) ++cnt[rk[i]];
    for (i=1;i<=m;++i) cnt[i]+=cnt[i-1];
    for (i=n;i>=1;--i) sa[cnt[rk[i]]--]=i;
    
    for (w=1;w<n;w<<=1,m=p)
    {
        memset(cnt,0,sizeof(cnt));
        for (p=0,i=n;i>n-w;--i) sa2[++p]=i;
        for (i=1;i<=n;++i) if (sa[i]>w) sa2[++p]=sa[i]-w;
        for (i=1;i<=n;++i) px[i]=rk[sa2[i]];
        for (i=1;i<=n;++i) ++cnt[px[i]];
        for (i=1;i<=m;++i) cnt[i]+=cnt[i-1];
        for (i=n;i>=1;--i) sa[cnt[px[i]]--]=sa2[i];
        swap(sa2,rk);
        for (p=0,i=1;i<=n;++i) rk[sa[i]]=cmp(sa[i],sa[i-1],w)?p:++p;
    }
    
    for (i=1;i<=n;++i) write(sa[i]),*sti++=' ';
    *sti++='\n';
    
    for (i=1,k=0;i<=n;++i)
    {
        if (k) --k;
        while (s[sa[rk[i]-1]+k]==s[i+k]) ++k;
        height[rk[i]]=k;
    }
    
    for (i=2;i<=n;++i) write(height[i]),*sti++=' ';
    
    fwrite(Buff,1,sti-Buff,stdout);
    
    return 0;
}

评测结果