TLE on #8#9#10

用的 SA-IS

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

#define N 4000010

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

namespace SA_IS {
    #define N 4000010

    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 or s[x]!=s[y] or tpy[x]!=tpy[y]) return 0;
        for (int i=1;x+i<len;i++) {
            if (s[x+i]!=s[y+i] or tpy[x+i]!=tpy[y+i]
                or 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 *sa,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 *sa,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,sa,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,sa,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,sa,sigma);
        delete[] tpy,tmp,s1,tLMS;
        return;
    }

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

    #undef N
}

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