感觉以前听ly神犇说过吧。就是贪心地选择后缀排名更小的。
证明可以戳这里看看：传送门
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
#define ll long long
#define inf 0x3f3f3f3f
#define N 400010
inline char gc(){
static char buf[1<<16],*S,*T;
if(S==T){T=(S=buf)+fread(buf,1,1<<16,stdin);if(T==S) return EOF;}
return *S++;
}
inline int read(){
int x=0,f=1;char ch=gc();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=gc();}
while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=gc();
return x*f;
}
int n1,n2,n,m,a[N],rk[N<<1],rk1[N],sa[N],tmp[N],cnt[N];
int main(){
// freopen("a.in","r",stdin);
n1=read();for(int i=1;i<=n1;++i) a[i]=read();n=n1;a[++n]=m=1001;
n2=read();for(int i=1;i<=n2;++i) a[++n]=read();
for(int i=1;i<=n;++i) cnt[a[i]]=1;
for(int i=1;i<=m;++i) cnt[i]+=cnt[i-1];
for(int i=1;i<=n;++i) rk[i]=cnt[a[i]];
int k=0;
for(int p=1;k!=n;p+=p,m=k){
for(int i=1;i<=m;++i) cnt[i]=0;
for(int i=1;i<=n;++i) cnt[rk[i+p]]++;
for(int i=1;i<=m;++i) cnt[i]+=cnt[i-1];
for(int i=n;i>=1;--i) tmp[cnt[rk[i+p]]--]=i;
for(int i=1;i<=m;++i) cnt[i]=0;
for(int i=1;i<=n;++i) cnt[rk[tmp[i]]]++;
for(int i=1;i<=m;++i) cnt[i]+=cnt[i-1];
for(int i=n;i>=1;--i) sa[cnt[rk[tmp[i]]]--]=tmp[i];
memcpy(rk1,rk,sizeof(rk1));rk[sa[1]]=k=1;
for(int i=2;i<=n;++i){
if(rk1[sa[i]]!=rk1[sa[i-1]]||rk1[sa[i]+p]!=rk1[sa[i-1]+p]) ++k;
rk[sa[i]]=k;
}
}int p1=1,p2=n1+2;
while(p1<=n1&&p2<=n){
if(rk[p1]<rk[p2]) printf("%d ",a[p1++]);
else printf("%d ",a[p2++]);
}while(p1<=n1) printf("%d ",a[p1++]);
while(p2<=n) printf("%d ",a[p2++]);
return 0;
}