为什么我的SA一直TLE，大佬来看看

SA模板测试

这道题一直TLE

#include <bits/stdc++.h>
#define ll long long
#define pa pair<int,int>
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define YES {puts("YES");return;}
#define NO {puts("NO");return ;}
using namespace std;
const int maxn=1e6+1011;
const int MOD=998244353;
const int inf=2147483647;
const double pi=acos(-1);
const double eps=1e-12;


ll read(){
    ll x=0,f=1;char ch=getchar();
    for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
    for(;isdigit(ch);ch=getchar())x=x*10+ch-'0';
    return x*f;
}


struct SA{ 
	string ch;
	int n,M=30;
	int sa[maxn],rk[maxn],tp[maxn],tax[maxn],height[maxn];
	
	void Qsort(){					
		for(int i=0;i<=M;i++)tax[i]=0;
		for(int i=1;i<=n;i++)tax[rk[i]]++;
		for(int i=1;i<=M;i++)tax[i]+=tax[i-1];
		for(int i=n;i>=1;i--)sa[ tax[rk[tp[i]]]-- ]=tp[i];
		return ;
	}
	
	void get_sa(string s){
		ch=s;n=s.length();
		ch="!"+ch;
		for(int i=1;i<=n;i++)rk[i]=ch[i]-'a'+1,tp[i]=i;
		Qsort();
		for(int w=1,p=0;w<=n;w<<=1,M=p){
			p=0;
			for(int i=n-w+1;i<=n;i++)tp[++p]=i;
			for(int i=1;i<=n;i++)if(sa[i]>w)tp[++p]=sa[i]-w;
			Qsort();swap(tp,rk);rk[sa[1]]=p=1;
			for(int i=2;i<=n;i++){
				if(tp[sa[i-1]]==tp[sa[i]] && tp[sa[i-1]+w]==tp[sa[i]+w])rk[sa[i]]=p;
				else rk[sa[i]]=++p;
			}
			if(p==n)break;
		}
		return ;
	}
	
	void get_height(){
		for(int i=1;i<=n;i++)rk[sa[i]]=i;
		height[0]=0;
		for(int i=1,k=0;i<=n;i++){
			if(rk[i]==1)continue;
			if(k)k--;
			int j=sa[rk[i]-1];
			while(i+k<=n && j+k<=n && ch[i+k]==ch[j+k])k++;
			height[rk[i]]=k;
		}
		return ;
	}
	
}S;
void solve(){
	string s;cin>>s;
	S.get_sa(s);S.get_height();
	for(int i=1;i<=S.n;i++)printf("%d ",S.sa[i]);puts("");
	for(int i=1;i<=S.n;i++)printf("%d ",S.height[i]);puts("");
	return ;
}
int main(){
	int t=read();
	while(t--)solve();
	return 0;
}


``