用的 SA-IS

但是 #8#9#10 跑的巨慢（本地可以跑出来）

怀疑是哪里写假了

#include <iostream>
#include <cstring>
#include <cstdio>
#include <string>

#define N 2000010

using namespace std;
char s[N];
int len,sa[N];

bool isLMS(int x,bool *tpy) {
    if (x<=0 or !tpy[x] or tpy[x-1]) return 0;
    return 1;
}

template<typename T>
bool sameLMS(int x,int y,bool *tpy,T s,int len) {
    if (x==-1 or y==-1) return 0;
    for (int i=0;;i++) {
        if (s[x+i]!=s[y+i] or tpy[x+i]!=tpy[y+i]) return 0;
        if (!i) continue;
        if (isLMS(x+i,tpy)!=isLMS(y+i,tpy)) return 0;
        if (isLMS(x+i,tpy)) return 1;
    }
}

template<typename T>
void inducedSort(T s,int len,bool *tpy,int *LMS,int LMScnt,int sigma) {
    int *tong=new int[sigma];
    int *sum=new int[sigma];
    memset(sa,-1,sizeof(sa[0])*len);
    memset(tong,0,sizeof(tong[0])*sigma);
    for (int i=0;i<len;i++) tong[s[i]]++;
    sum[0]=tong[0];
    for (int i=1;i<sigma;i++) sum[i]=sum[i-1]+tong[i];
    for (int i=LMScnt-1;i>=0;i--) sa[--sum[s[LMS[i]]]]=LMS[i];
    sum[0]=0;
    for (int i=1;i<sigma;i++) sum[i]=sum[i-1]+tong[i-1];
    for (int i=0;i<len;i++) {
        if (sa[i]<=0) continue;
        if (!tpy[sa[i]-1]) sa[sum[s[sa[i]-1]]++]=sa[i]-1;
    }
    sum[0]=tong[0];
    for (int i=1;i<sigma;i++) sum[i]=sum[i-1]+tong[i];
    for (int i=len-1;i>=0;i--) {
        if (sa[i]<=0) continue;
        if (tpy[sa[i]-1]) sa[--sum[s[sa[i]-1]]]=sa[i]-1;
    }
    delete[] tong,sum;
    return;
}

template<typename T>
void sais(T s,int len,int *LMS,int sigma) {
    bool *tpy=new bool[len];
    tpy[len-1]=1;
    for (int i=len-2;i>=0;i--) {
        if (s[i]>s[i+1]) tpy[i]=0;
        else if (s[i]<s[i+1]) tpy[i]=1;
        else tpy[i]=tpy[i+1];
    }
    int LMScnt=0;
    for (int i=0;i<len;i++)
        if (isLMS(i,tpy)) LMS[LMScnt++]=i;
    inducedSort(s,len,tpy,LMS,LMScnt,sigma);
    int *tmp=new int[len],cnt=0,pre=-1;
    for (int i=0;i<len;i++) {
        if (!isLMS(sa[i],tpy)) continue;
        if (!sameLMS(sa[i],pre,tpy,s,len)) ++cnt;
        tmp[sa[i]]=cnt-1,pre=sa[i];
    }
    int *s1=new int[LMScnt]; LMScnt=0;
    for (int i=0;i<len;i++) {
        if (!isLMS(i,tpy)) continue;
        s1[LMScnt++]=tmp[i];
    }
    int *tLMS=new int[LMScnt];
    if (cnt<LMScnt) sais(s1,LMScnt,tLMS,cnt);
    else for (int i=0;i<LMScnt;i++) sa[s1[i]]=i;
    for (int i=0;i<LMScnt;i++) tLMS[i]=LMS[sa[i]];
    inducedSort(s,len,tpy,tLMS,LMScnt,sigma);
    delete[] tpy,tmp,s1,tLMS;
    return;
}

void init(string s,int len,int sigma) {
    int *LMS=new int[N];
    sais(s,len+1,LMS,sigma);
    delete[] LMS;
    for (int i=0;i<len;i++) sa[i]=sa[i+1]+1;
}

int main() {
    cin>>s; int len=strlen(s);
    init(s,len,128);
    for (int i=0;i<len;i++) printf("%d ",sa[i]);
    return 0;
}