求助SA算法

#include<bits/stdc++.h>
#define printlf(x) print(x),putchar('\n')
#define printsp(x) print(x),putchar(' ')
using namespace std;
inline int read(){
    int x=0;
    bool w=0;
    char c=getchar();
    while(!isdigit(c))  w|=c=='-',c=getchar();
    while(isdigit(c))   x=(x<<1)+(x<<3)+(c^48),c=getchar();
    return w?-x:x;
}
inline void print(int x){
    if(x<0) x=-x,putchar('-');
    if(x>9) print(x/10);
    putchar('0'+x%10);
}
const int N=5e5+5;
int ans[N],saA[N],saB[N],rkA[N],rkB[N],oldrk[N];
string a="?",b,s;
int n,w,cnt;
inline bool cmpA(int x,int y){
	return rkA[x]==rkA[y]?rkA[x+w]<rkA[y+w]:rkA[x]<rkA[y];
}
inline void Get_saA(){求后缀
	for(register int i=1;i<=n;++i)	saA[i]=i,rkA[i]=a[i];
	for(w=1;w<n;w<<=1){
		sort(saA+1,saA+1+n,cmpA);
		memcpy(oldrk,rkA,sizeof(rkA));
		for(register int i=1,p=0;i<=n;++i)
			if(oldrk[saA[i]]==oldrk[saA[i-1]] && oldrk[saA[i]+w]==oldrk[saA[i-1]+w])	rkA[saA[i]]=p;
			else	rkA[saA[i]]=++p;
	}
}
inline bool cmpB(int x,int y){
	return rkB[x]==rkB[y]?rkB[x+w]<rkB[y+w]:rkB[x]<rkB[y];
}
inline void Get_saB(){//求前缀
	for(register int i=1;i<=n;++i)	saB[i]=i,rkB[i]=b[i];	
	for(w=1;w<n;w<<=1){
		sort(saB+1,saB+1+n,cmpB);
		memcpy(oldrk,rkB,sizeof(rkB));
		for(register int i=1,p=0;i<=n;++i)
			if(oldrk[saB[i]]==oldrk[saB[i-1]] && oldrk[saB[i]+w]==oldrk[saB[i-1]+w])	rkB[saB[i]]=p;
			else	rkB[saB[i]]=++p;
	}
}
signed main(){
	n=read();
	for(register int i=1;i<=n;++i){
		char ch;cin>>ch;s+=ch;
	}
	a+=s,b=s+'?';reverse(b.begin(),b.end());
//	cout<<a<<endl<<b<<endl;
//	cout<<a[0]<<' '<<b[0]<<endl;
	Get_saA();
	Get_saB();
//	cout<<"saA:";
//	for(register int i=1;i<=n;++i)	cout<<saA[i]<<' ';
//	cout<<"\nsaB:";
//	for(register int i=1;i<=n;++i)	cout<<saB[i]<<' ';cout<<endl;
//	cout<<"rkA:";for(register int i=1;i<=n;++i)	cout<<rkA[i]<<' ';cout<<endl;
//	cout<<"rkB:";for(register int i=1;i<=n;++i)	cout<<rkB[i]<<' ';cout<<endl;
	int l=1,r=n;
	while(l<=r){
		if(a[l]<a[r])	ans[++cnt]=l++;
		else	if(a[l]>a[r])	ans[++cnt]=r--;
		else{
			if(rkA[l]<=rkB[r])	ans[++cnt]=l++;//上文核心判断
			else	ans[++cnt]=r--;
		}
	}
//	for(register int i=1;i<=n;++i)	cout<<ans[i]<<' ';cout<<endl;
	for(register int i=1;i<=cnt;++i)
		if(i%80==0)cout<<a[ans[i]]<<endl;
		else	cout<<a[ans[i]];
    return 0;
}