代码

#include<bits/stdc++.h>
#define file(F) freopen(#F".in","r",stdin),freopen(#F".out","w",stdout)
using namespace std;
using ll=long long;
void Solve();
const int N = 1e6+16;
int n;
string s;
int sa[N],rk[N],oldrk[N];
bool cmp(int x,int y,int w) {
   return oldrk[x]==oldrk[y]&&(x+w>=n?y+w>=n:oldrk[x+w]==oldrk[y+w]);
}
void suffix_array() {
   int m=127;
   vector<int> cnt(m+1),key1(n),id(n);
   for(int i=0;i<n;i++) cnt[rk[i]=s[i]]++;
   for(int i=1;i<=m;i++) cnt[i]+=cnt[i-1];
   for(int i=n-1;i>=0;i--) sa[--cnt[rk[i]]]=i;
   for(int w=1;w<n;w<<=1) {
      int p=0;
      for(int i=n-1;i>=n-w;i--) id[p++]=i;
      for(int i=0;i<n;i++) if(sa[i]>=w) id[p++]=sa[i]-w;
      vector<int>(m+1,0).swap(cnt);
      for(int i=0;i<n;i++) cnt[key1[i]=rk[id[i]]]++;
      for(int i=1;i<=m;i++) cnt[i]+=cnt[i-1];
      for(int i=n-1;i>=0;i--) sa[--cnt[key1[i]]]=id[i];
      memcpy(oldrk,rk,n<<2);
      rk[sa[0]]=m=0;
      for(int i=1;i<n;i++) rk[sa[i]]=cmp(sa[i],sa[i-1],w)?m:++m;
      if(++m==n) break;
   }
}
int height[N];
void lcp_array() {
   int h=0;
   for(int i=0;i<n;i++) if(rk[i]) {
      if(h) --h;
      while(s[i+h]==s[sa[rk[i]-1]+h]) ++h;
      height[rk[i]]=h;
   }
}
signed main() {
#ifndef ONLINE_JUDGE

#endif
   cin.tie(nullptr)->sync_with_stdio(false);
   Solve();
   return 0;
}
void Solve() {
   cin>>s; n=s.size();
   suffix_array();
   for(int i=0;i<n;i++) printf("%d ",sa[i]+1); puts("");
   lcp_array();
   for(int i=1;i<n;i++) printf("%d ",height[i]); puts("");
}

评测结果