自动搬运

查看原文

来自洛谷，原作者为

	BitByBit a.k.a. 海绵猴子

搬运于2025-08-24 22:35:14，当前版本为作者最后更新于2025-08-19 13:26:16，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

思路

令要归并的串为 $A,B$。当前 $A,B$ 分别比较到了第 $i,j$ 位。首先若 $A_i \ne B_j$ 则可以直接让字典序更小的去归并。否则考虑 $A_{i+1},B_{j+1}$ 的大小，若相等则考虑 $A_{i+2},B_{j+2}$ 的大小，以此类推。

不难发现就是比较 $i,j$ 对应的后缀的字典序，归并字典序小的。于是把两个串拼到一起建立后缀数组即可。

记得 $A,B$ 中间放一个巨大的字符，防止两串之间相互影响。

程序

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n1;
	for(int i=1;i<=n1;i++)cin>>A[i];
	A[n1+1]=5000;
	cin>>n2;
	for(int i=n1+2;i<=n1+1+n2;i++)cin>>A[i];
	A[n1+n2+2]=5000;
	n=n1+n2+2;
	suffix_sort();//对 A 数组后缀排序。
	for(int i=1,j=n1+2,k=1;k<=n1+n2;k++)
		if(Rank[i]<Rank[j])cout<<A[i]<<' ',i++;
		else cout<<A[j]<<' ',j++;
	return 0;
}