【题意】
给定两个字符串，求二路归并后最小字典序的字符串。
【思路】
连接两个字符串后求出rank数组。通过比较rank数组进行二路归并。
【代码】
1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 #include<algorithm> 5 #define FOR(a,b,c) for(int a=b;a<=c;a++) 6 using namespace std; 7 8 typedef long long ll; 9 const int N = 4e3+10; 10 11 ll read() 12 { 13 char c=getchar(); 14 ll f=1,x=0; 15 while(!isdigit(c)) { 16 if(c=='-') f=-1; 17 c=getchar(); 18 } 19 while(isdigit(c)) 20 x=x*10+c-'0', 21 c=getchar(); 22 return x*f; 23 } 24 25 int s[N]; 26 int t[N],t2[N],c[N],sa[N],rank[N]; 27 28 void build_sa(int m,int n) 29 { 30 int *x=t,*y=t2; 31 FOR(i,0,m-1) c[i]=0; 32 FOR(i,0,n-1) c[x[i]=s[i]]++; 33 FOR(i,0,m-1) c[i]+=c[i-1]; 34 for(int i=n-1;i>=0;i--) sa[--c[x[i]]]=i; 35 for(int k=1;k<=n;k<<=1) { 36 int p=0; 37 FOR(i,n-k,n-1) y[p++]=i; 38 FOR(i,0,n-1) if(sa[i]>=k) y[p++]=sa[i]-k; 39 40 FOR(i,0,m-1) c[i]=0; 41 FOR(i,0,n-1) c[x[y[i]]]++; 42 FOR(i,0,m-1) c[i]+=c[i-1]; 43 for(int i=n-1;i>=0;i--) sa[--c[x[y[i]]]]=y[i]; 44 45 swap(x,y); 46 p=1; x[sa[0]]=0; 47 FOR(i,1,n-1) 48 x[sa[i]]=y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k]?p-1:p++; 49 if(p>=n) break; 50 m=p; 51 } 52 } 53 void get_rank(int n) 54 { 55 FOR(i,0,n-1) rank[sa[i]]=i; 56 } 57 58 int n,m,len,a[N],b[N],ans[N]; 59 60 int main() 61 { 62 n=read(); 63 FOR(i,0,n-1) a[i]=read(),s[len++]=a[i]; 64 s[len++]=1001; 65 m=read(); 66 FOR(i,0,m-1) b[i]=read(),s[len++]=b[i]; 67 s[len++]=1001; 68 69 build_sa(1003,len); 70 get_rank(len); 71 72 int p1=0,p2=0,tot=0; 73 while(p1<n || p2<m) { 74 if(p1>=n) printf("%d ",b[p2++]); 75 else if(p2>=m) printf("%d ",a[p1++]); 76 else { 77 if(rank[p1]<rank[n+1+p2]) printf("%d ",a[p1++]); 78 else printf("%d ",b[p2++]); 79 } 80 } 81 return 0; 82 }