后缀数组模板（倍增）

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

char str[1000005];
int x[1000005],y[1000005],u[1000005],v[1000005],r[1000005],o[1000005],m=256,n;

int main(){
    scanf("%s",str+1);
    n=strlen(str+1);
    
    for(int i=1;i<=n;i++) u[str[i]]++;
    for(int i=1;i<=m;i++) u[i]+=u[i-1];
    for(int i=n;i>=1;i--) x[u[str[i]]--]=i;
    r[x[1]]=1;
    for(int i=2;i<=n;i++) r[x[i]]=r[x[i-1]]+((str[x[i]]-str[x[i-1]])?1:0);
    
    for(int l=1;r[x[n]]<n;l<<=1) {
        memset(u,0,sizeof u);
        memset(v,0,sizeof v);
        memcpy(o,r,sizeof r);
        for(int i=1;i<=n;i++) u[r[i]]++, v[(i+l<=n)?r[i+l]:0]++;
        for(int i=1;i<=n;i++) u[i]+=u[i-1], v[i]+=v[i-1];
        for(int i=n;i>=1;i--) y[v[(i+l<=n)?r[i+l]:0]--]=i;
        for(int i=n;i>=1;i--) x[u[r[y[i]]]--]=y[i];
        r[x[1]]=1;
        for(int i=2;i<=n;i++) 
            r[x[i]]=r[x[i-1]]+((o[x[i]] != o[x[i-1]])  ||  (((x[i]+l<=n)?o[x[i]+l]:0) != ((x[i-1]+l<=n)?o[x[i-1]+l]:0)));
    }
    for(int i=1;i<=n;i++) printf("%d ",x[i]);
}