题链：
http://www.lydsy.com/JudgeOnline/problem.php?id=4278
题解：
把两个串连接起来，用一个大数连接（必须要用大数）。
倍增算法求出后缀排名。
然后两个指针指向A,B串，每次比较两个后缀的大小，
优先取出小的那个后缀的首字母，然后对应指针向后移动一位。
代码：
#include<cstdio>
#include<cstring>
#include<iostream>
#define MAXN 450000
#define filein(x) freopen(#x".in","r",stdin);
#define fileout(x) freopen(#x".out","w",stdout);
using namespace std;
int sa[MAXN],rak[MAXN],hei[MAXN];
int A[MAXN],B[MAXN],T[MAXN];
int LA,LB;
void build(int N,int M){
static int cc[MAXN],ta[MAXN],tb[MAXN],*x,*y,h,p;
x=ta; y=tb; h=0; T[N]=-1;
for(int i=0;i<M;i++) cc[i]=0;
for(int i=0;i<N;i++) cc[x[i]=T[i]]++;
for(int i=1;i<M;i++) cc[i]+=cc[i-1];
for(int i=N-1;i>=0;i--) sa[--cc[x[i]]]=i;
for(int k=1;p=0,k<N;k<<=1){
for(int i=N-k;i<N;i++) y[p++]=i;
for(int i=0;i<N;i++) if(sa[i]>=k) y[p++]=sa[i]-k;
for(int i=0;i<M;i++) cc[i]=0;
for(int i=0;i<N;i++) cc[x[y[i]]]++;
for(int i=1;i<M;i++) cc[i]+=cc[i-1];
for(int i=N-1;i>=0;i--) sa[--cc[x[y[i]]]]=y[i];
swap(x,y); y[N]=-1; x[sa[0]]=0; M=1;
for(int i=1;i<N;i++)
x[sa[i]]=y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k]?M-1:M++;
if(M>=N) break;
}
for(int i=0;i<N;i++) rak[sa[i]]=i;
for(int i=0,j;i<N;i++){
if(h) h--;
if(rak[i]){
j=sa[rak[i]-1];
while(T[i+h]==T[j+h]) h++;
}
hei[rak[i]]=h;
}
}
void solve(){
int i=0,j=0,ii,jj,h;
while(i<LA&&j<LB){
ii=i; jj=LA+1+j;
if(rak[ii]<rak[jj]) printf("%d ",A[i++]);
else printf("%d ",B[j++]);
}
while(i<LA) printf("%d ",A[i++]);
while(j<LB) printf("%d ",B[j++]);
}
int main()
{
int N; scanf("%d",&LA);
for(int i=0;i<LA;i++) scanf("%d",&A[i]),T[i]=A[i];
T[LA]=1001; scanf("%d",&LB);
for(int i=0;i<LB;i++) scanf("%d",&B[i]),T[LA+1+i]=B[i];
N=LA+LB+1;
build(N,1005);
solve();
return 0;
}
●BZOJ 4278 [ONTAK2015]Tasowanie
原文：http://www.cnblogs.com/zj75211/p/7994016.html