代码

#include<bits/stdc++.h>
using namespace std;
int sa[100005],rk[100005],ht[100005];
char s[100005];
void getsa(int n,char *s,int sa[],int m=122)
{
  int x[100005],y[100005],b[100005];
  memset(x,0,sizeof(x)),memset(y,0,sizeof(y)),memset(b,0,sizeof(b));
  for(int i=1;i<=n;i++)b[x[i]=s[i]]++;
  for(int i=2;i<=m;i++)b[i]+=b[i-1];
  for(int i=n;i>=1;i--)sa[b[x[i]]--]=i;
  for(int k=1;k<=n;k<<=1)
  {
    int p=0;
    for(int i=n-k+1;i<=n;i++)y[++p]=i;
    for(int i=1;i<=n;i++)if(sa[i]>k)y[++p]=sa[i]-k;
    memset(b,0,sizeof(b));
    for(int i=1;i<=n;i++)b[x[i]]++;
    for(int i=2;i<=m;i++)b[i]+=b[i-1];
    for(int i=n;i>=1;i--)sa[b[x[y[i]]]--]=y[i];
    swap(x,y),x[sa[1]]=1,p=1;
    for(int i=2;i<=n;i++)x[sa[i]]=(y[sa[i]]^y[sa[i-1]]||y[sa[i]+k]^y[sa[i-1]+k])?++p:p;
    if(p==n)break;
    m=p;
  }
}
void getht(int n,char *s,int sa[],int rk[],int ht[]){
  int hi=0;
  for(int i=1;i<=n;i++)rk[sa[i]]=i;
  for(int i=1;i<=n;i++)
  {
    if(rk[i]==1)continue;
    if(hi)hi--;
    while(sa[rk[i]-1]+hi<=n&&i+hi<=n&&s[i+hi]==s[sa[rk[i]-1]+hi])hi++;
    ht[rk[i]]=hi;
  }
}
int main(){
  scanf("%s",s+1);
  getsa(strlen(s+1),s,sa),getht(strlen(s+1),s,sa,rk,ht);
  for(int i=1;i<=strlen(s+1);i++)cout<<sa[i]<<(i==strlen(s+1)?'\n':' ');
  for(int i=2;i<=strlen(s+1);i++)cout<<ht[i]<<(i==strlen(s+1)?'\n':' ');
  return 0;
}

评测结果