题解：P8023 [ONTAK2015] Tasowanie

· · 题解

思路

令要归并的串为 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;
}