SA_IS

template<size_t size>
struct SuffixArray{
    bool type[size<<1];
    int bucket[size],bucket1[size];
    int sa[size],rk[size],ht[size];
    inline bool isLMS(const int i,const bool *type){return i>0&&type[i]&&!type[i-1];}
    template<class T>
    inline void inducedSort(T s,int*sa,int len,int sigma,int bucketSize,bool*type,int*bucket,int*cntbuf,int*p){
        memset(bucket,0,sizeof(int)*sigma),memset(sa,-1,sizeof(int)*len);
        register int i;
        for(i=0;i<len;++i)++bucket[s[i]];
        cntbuf[0]=bucket[0];
        for(i=1;i<sigma;++i)cntbuf[i]=cntbuf[i-1]+bucket[i];
        for(i=bucketSize-1;~i;--i)sa[--cntbuf[s[p[i]]]]=p[i];
        for(i=1;i<sigma;++i)cntbuf[i]=cntbuf[i-1]+bucket[i-1];
        for(i=0;i<len;++i)if(sa[i]>0&&!type[sa[i]-1])sa[cntbuf[s[sa[i]-1]]++]=sa[i]-1;
        cntbuf[0]=bucket[0];
        for(i=1;i<sigma;++i)cntbuf[i]=cntbuf[i-1]+bucket[i];
        for(i=len-1;~i;--i)if(sa[i]>0&&type[sa[i]-1])sa[--cntbuf[s[sa[i]-1]]]=sa[i]-1;
    }
    template<typename T>
    inline void sais(T s,int*sa,int len,bool*type,int*bucket,int*bucket1,int sigma) {
        register int i,j,x;
        int bucketSize=0,cnt=0,p=-1,*cntbuf=bucket+sigma;
        type[len-1]=1;
        for(i=len-2;~i;--i)type[i]=s[i]<s[i+1]||s[i]==s[i+1]&&type[i+1];
        for(i=1;i<len;++i)if(type[i]&&!type[i-1])bucket1[bucketSize++]=i;
        inducedSort(s,sa,len,sigma,bucketSize,type,bucket,cntbuf,bucket1);
        for(i=bucketSize=0;i<len;++i)if(isLMS(sa[i],type))sa[bucketSize++]=sa[i];
        for(i=bucketSize;i<len;++i)sa[i]=-1;
        for(i=0;i<bucketSize;++i){
            x=sa[i];
            for(j=0;j<len;++j) {
                if(p==-1||s[x+j]!=s[p+j]||type[x+j]!=type[p+j]){cnt++,p=x;break;}
                else if(j>0&&(isLMS(x+j,type)||isLMS(p+j,type)))break;
            }
            x=(~x&1?x>>1:x-1>>1);
            sa[bucketSize+x]=cnt-1;
        }
        for(i=j=len-1;i>=bucketSize;--i)if(~sa[i])sa[j--]=sa[i];
        int *s1=sa+len-bucketSize,*bucket2=bucket1+bucketSize;
        if(cnt<bucketSize)sais(s1,sa,bucketSize,type+len,bucket,bucket1+bucketSize,cnt);
        else for(i=0;i<bucketSize;++i)sa[s1[i]]=i;
        for(i=0;i<bucketSize;++i)bucket2[i]=bucket1[sa[i]];
        inducedSort(s,sa,len,sigma,bucketSize,type,bucket,cntbuf,bucket2);
    }
    template<typename T>
    inline void getHeight(T s,int len,int*sa){
        register int i,j,k;
        for(i=k=0;i<len;++i){
            if(!rk[i])k=0;
            else{
                if(k>0)--k;
                j=sa[rk[i]-1];
                while(i+k<len&&j+k<len&&s[i+k]==s[j+k])++k;
            }
            ht[rk[i]]=k;
        }
    }
    template<class T>
    inline void init(T s,int len,int sigma) {
        sais(s,sa,len,type,bucket,bucket1,sigma);
        for(int i=1;i<len;++i)rk[sa[i]]=i;
        getHeight(s,len,sa);
    }
};
注意事项：字符串从 0 开始，init时，len需要传入字符串长度n+1，simga需要传入字符集大小，init完毕后得到sa数组，0到n共n+1个后缀排序后的结果(sa[0]总是表示空串)，以及rk数组和ht数组(相邻后缀的lcp长度)。