rt，$O(n\log^2 n)$ 的哈希。

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+1,bas=200;
char s[N];
int n,a[N],p[N]={1},hsh[N],ans;
inline int get(int l,int r){
    return hsh[r]-hsh[l-1]*p[r-l+1];
}
inline bool cmp(int x,int y){
    ans=0;
    int l=-1,r=min(n-x,n-y);
    while(l<r){
        int mid=l+r+1>>1;
        if(get(x,x+mid)==get(y,y+mid)) l=mid;
        else r=mid-1;
    }
    ans=l+1;
    return s[x+l+1]<s[y+l+1];
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    scanf("%s",s+1);
    n=strlen(s+1);
    for(int i=1;i<=n;i++){
        p[i]=p[i-1]*bas;
        hsh[i]=hsh[i-1]*bas+s[i];
        a[i]=i;
    }
    stable_sort(a+1,a+1+n,cmp);
    for(int i=1;i<=n;i++) cout<<a[i]-1<<" ";
    cout<<endl;
    for(int i=1;i<=n;i++){
        cmp(a[i],a[i-1]);
        cout<<ans<<" ";
    }
}