BZOJ_4278_[ONTAK2015]Tasowanie

BZOJ_4278_[ONTAK2015]Tasowanie_后缀数组

Description

给定两个数字串A和B，通过将A和B进行二路归并得到一个新的数字串T，请找到字典序最小的T。

Input

第一行包含一个正整数n(1<=n<=200000)，表示A串的长度。

第二行包含n个正整数，其中第i个数表示A[i](1<=A[i]<=1000)。

第三行包含一个正整数m(1<=m<=200000)，表示B串的长度。

第四行包含m个正整数，其中第i个数表示B[i](1<=B[i]<=1000)。

Output

输出一行，包含n+m个正整数，即字典序最小的T串。

Sample Input

6
1 2 3 1 2 4
7
1 2 2 1 3 4 3

Sample Output

1 1 2 2 1 2 3 1 2 3 4 3 4

类似某道奶牛题，这道更简单一些？

归并的时候每次要选当前到串末尾字典序小的那个，并且每次选一个字符。

把两个串拼起来，求一遍后缀数组，这样就可以快速的知道两个后缀的字典序大小关系。

模拟即可。

代码：

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

#define N 400050

int ws[N],wv[N],wa[N],wb[N],r[N],n,Rank[N],height[N],sa[N],m,la,lb;

int a[N],b[N];

void build_suffix_array() {

	m=1002;

    int i,j,p,*x=wa,*y=wb,*t;

    for(i=0;i<m;i++) ws[i]=0;

    for(i=0;i<n;i++) ws[x[i]=r[i]]++;

    for(i=1;i<m;i++) ws[i]+=ws[i-1];

    for(i=n-1;i>=0;i--) sa[--ws[x[i]]]=i;

    for(p=j=1;p<n;j<<=1,m=p) {

        for(p=0,i=n-j;i<n;i++) y[p++]=i;

        for(i=0;i<n;i++) if(sa[i]-j>=0) y[p++]=sa[i]-j;

        for(i=0;i<n;i++) wv[i]=x[y[i]];

        for(i=0;i<m;i++) ws[i]=0;

        for(i=0;i<n;i++) ws[wv[i]]++;

        for(i=1;i<m;i++) ws[i]+=ws[i-1];

        for(i=n-1;i>=0;i--) sa[--ws[wv[i]]]=y[i];

        for(t=x,x=y,y=t,i=p=1,x[sa[0]]=0;i<n;i++) {

            if(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+j]==y[sa[i-1]+j]) x[sa[i]]=p-1;

            else x[sa[i]]=p++;

        }

    }

    for(i=1;i<n;i++) Rank[sa[i]]=i;

    for(i=p=0;i<n-1;height[Rank[i++]]=p)

        for(p?p--:0,j=sa[Rank[i]-1];r[i+p]==r[j+p];p++);

}

int main() {

	scanf("%d",&la);

	int i;

	for(i=0;i<la;i++) {

		scanf("%d",&a[i]);

		r[n++]=a[i];

	}

	scanf("%d",&lb);

	r[n++]=1001;

	for(i=0;i<lb;i++) {

		scanf("%d",&b[i]);

		r[n++]=b[i];

	}

	r[n++]=0;

	build_suffix_array();

	int j=0,k=la+1;

	while(j<la&&k<n-1) {

		if(Rank[j]<Rank[k]) printf("%d ",r[j++]);

		else printf("%d ",r[k++]);

	}

	while(j<la) printf("%d ",r[j++]);

	while(k<n-1) printf("%d ",r[k++]);

}

巴特西