rt 后缀数组没求错

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>

#define N 1000001

using namespace std;
int n,k,sa[N],rk[N],h[N],st[N][26];
char s[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,T s,int len,bool *tpy) {
    if (x<=0 or y<=0 or s[x]!=s[y] or tpy[x]!=tpy[y]) return 0;
    for (int i=1;x+i<len and y+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 inducesort(T s,int len,int *LMS,int LMScnt,bool *tpy,int sigma) {
    int *t=new int[sigma];
    int *sum=new int[sigma];
    memset(sa,-1,sizeof(sa[0])*len);
    memset(t,0,sizeof(t[0])*sigma);
    for (int i=0;i<len;i++) t[s[i]]++;
    sum[0]=t[0];
    for (int i=1;i<sigma;i++) sum[i]=sum[i-1]+t[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]+t[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]=t[0];
    for (int i=1;i<sigma;i++) sum[i]=sum[i-1]+t[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[] t,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;
    inducesort(s,len,LMS,LMScnt,tpy,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,s,len,tpy)) ++cnt;
        tmp[sa[i]]=cnt-1,pre=sa[i];
    }
    int *s1=new int[LMScnt];
    for (int i=0;i<LMScnt;i++) s1[i]=tmp[LMS[i]];
    int *tLMS=new int[LMScnt];
    if (LMScnt!=cnt) 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]];
    inducesort(s,len,tLMS,LMScnt,tpy,sigma);
    delete[] tpy,tmp,s1,tLMS;
    return;
}

void init(char *s,int len,int sigma) {
    int *LMS=new int[len];
    sais(s,len+1,LMS,sigma);
    delete[] LMS;
    for (int i=0;i<len;i++) sa[i]=sa[i+1];
    for (int i=0;i<len;i++) rk[sa[i]]=i;
    for (int i=0;i<len;i++) {
        if (!rk[i]) continue;
        h[rk[i]]=max(h[rk[i-1]]-1,0);
        while (s[i+h[rk[i]]]==s[sa[rk[i]-1]+h[rk[i]]]) ++h[rk[i]];
        st[rk[i]][0]=h[rk[i]];
    }
    for (int j=1;j<26;j++)
        for (int i=0;i+(1<<j)-1<len;i++) st[i][j]=min(st[i][j-1],st[i+(1<<(j-1))][j-1]);
}

int main() {
    scanf("%d%d",&n,&k);
    for (int i=0;i<n;i++) cin>>s[i];
    init(s,n,1000001);
    // for (int i=0;i<n;i++) printf("%d ",sa[i]);
    // printf("\n");
    // for (int i=0;i<n;i++) printf("%d ",rk[i]);
    // printf("\n");
    // for (int i=0;i<n;i++) printf("%d ",h[i]);
    // printf("\n");
    int ans=0,lg=log2(k-1);
    for (int i=0;i+k-2<n;i++) ans=max(ans,st[i][lg]);
    printf("%d\n",ans);
    return 0;
}