后缀数组20分WA，悬关，求调

#include<bits/stdc++.h>
using namespace std;
#define int long long 
const int N=600005;
const int M=600005; 
int T,n,ans,lg[N],g[N],f[N];
string a;
struct HZSZ{
	int rk[M],y[M],hei[M],sa[M],c[M],st[N][20];
	inline void get_sa(){
		memset(rk,0,sizeof(rk)),memset(y,0,sizeof(y)),memset(hei,0,sizeof(hei)),memset(sa,0,sizeof(sa)),memset(c,0,sizeof(c));
		int m=127; 
		for(int i=1;i<=n;++i) ++c[rk[i]=a[i]];
		for(int i=1;i<=m;++i) c[i]+=c[i-1];
		for(int i=n;i;--i) sa[c[rk[i]]--]=i;
		for(int k=1;k<=n;k<<=1){
			memset(c,0,sizeof(c)),memcpy(y,sa,sizeof(sa)); 
			for(int i=1;i<=n;++i) ++c[rk[y[i]+k]];
			for(int i=1;i<=m;++i) c[i]+=c[i-1];
			for(int i=n;i;--i) sa[c[rk[y[i]+k]]--]=y[i];
			memset(c,0,sizeof(c)),memcpy(y,sa,sizeof(sa)); 
			for(int i=1;i<=n;++i) ++c[rk[y[i]]];
			for(int i=1;i<=m;++i) c[i]+=c[i-1];
			for(int i=n;i;--i) sa[c[rk[y[i]]]--]=y[i];
			memcpy(y,rk,sizeof(rk));
			m=0;
			for(int i=1;i<=n;++i){
				if(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k]) rk[sa[i]]=m;
				else rk[sa[i]]=++m;
			}
			if(m==n) break; 
		}
		return ;
	}
	inline void get_hei(){
		for(int i=1;i<=n;++i) rk[sa[i]]=i;
		int k=0;
		for(int i=1;i<=n;++i){
			if(rk[i]==1) continue;
			if(k) --k;
			int j=sa[rk[i]-1];
			while(i+k<=n&&j+k<=n&&a[i+k]==a[j+k]) ++k;
			hei[rk[i]]=k;
		}
		return ; 
	}
	inline void build_ST(){
		memset(st,0x3f,sizeof(st));
		for(int i=1;i<=n;++i) st[0][i]=hei[i];
		for(int i=1;i<=15;++i){
			for(int j=1;j<=n;++j){
				st[i][j]=min(st[i-1][j],st[i-1][j+(1<<(i-1))]);
			}
		}
		return ;
	}
	inline int query(int x,int y){
		int mfx=min(rk[x],rk[y])+1,mfy=max(rk[y],rk[x]);
		int le=lg[mfy-mfx+1];
		return min(st[le][mfx],st[le][mfy-(1<<le)+1]); 
	}
}A,B;
signed main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	for(int i=2;i<=N-5;++i) lg[i]=lg[i>>1]+1;
	cin>>T;
	for(int MF=1;MF<=T;++MF){
		ans=0;
		a.clear();
		cin>>a;
		n=a.size();
		a=' '+a; 
		A.get_sa(),A.get_hei(),A.build_ST();
		reverse(&a[1],&a[n+1]);
		B.get_sa(),B.get_hei(),B.build_ST();
		memset(f,0,sizeof(f)); 
		memset(g,0,sizeof(g)); 
		for(int len=1;len<=n/2;++len){
			for(int i=len,j=len+i;j<=n;j+=len,i+=len){
				int lcp=min(A.query(i,j),len),lcs=min(len-1,B.query(n-i+2,n-j+2));
				int t=lcp+lcs-len+1;
				if(t>0) ++g[i-lcs],--g[i-lcs+t],++f[j+lcp-t],--f[j+lcp];
			}
		}
		for(int i=1;i<=n;++i) g[i]+=g[i-1],f[i]+=f[i-1];
		for(int i=1;i<n;++i) ans+=f[i]*g[i+1];
		cout<<ans<<'\n';
	}
	return 0;
}