bzoj 4278 [ONTAK2015]Tasowanie(SA,贪心)

时间:2022-08-07 09:57:00

【题意】

给定两个字符串,求二路归并后最小字典序的字符串。

【思路】

连接两个字符串后求出rank数组。通过比较rank数组进行二路归并。

【代码】

 #include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define FOR(a,b,c) for(int a=b;a<=c;a++)
using namespace std; typedef long long ll;
const int N = 4e3+; ll read()
{
char c=getchar();
ll f=,x=;
while(!isdigit(c)) {
if(c=='-') f=-;
c=getchar();
}
while(isdigit(c))
x=x*+c-'',
c=getchar();
return x*f;
} int s[N];
int t[N],t2[N],c[N],sa[N],rank[N]; void build_sa(int m,int n)
{
int *x=t,*y=t2;
FOR(i,,m-) c[i]=;
FOR(i,,n-) c[x[i]=s[i]]++;
FOR(i,,m-) c[i]+=c[i-];
for(int i=n-;i>=;i--) sa[--c[x[i]]]=i;
for(int k=;k<=n;k<<=) {
int p=;
FOR(i,n-k,n-) y[p++]=i;
FOR(i,,n-) if(sa[i]>=k) y[p++]=sa[i]-k; FOR(i,,m-) c[i]=;
FOR(i,,n-) c[x[y[i]]]++;
FOR(i,,m-) c[i]+=c[i-];
for(int i=n-;i>=;i--) sa[--c[x[y[i]]]]=y[i]; swap(x,y);
p=; x[sa[]]=;
FOR(i,,n-)
x[sa[i]]=y[sa[i]]==y[sa[i-]]&&y[sa[i]+k]==y[sa[i-]+k]?p-:p++;
if(p>=n) break;
m=p;
}
}
void get_rank(int n)
{
FOR(i,,n-) rank[sa[i]]=i;
} int n,m,len,a[N],b[N],ans[N]; int main()
{
n=read();
FOR(i,,n-) a[i]=read(),s[len++]=a[i];
s[len++]=;
m=read();
FOR(i,,m-) b[i]=read(),s[len++]=b[i];
s[len++]=; build_sa(,len);
get_rank(len); int p1=,p2=,tot=;
while(p1<n || p2<m) {
if(p1>=n) printf("%d ",b[p2++]);
else if(p2>=m) printf("%d ",a[p1++]);
else {
if(rank[p1]<rank[n++p2]) printf("%d ",a[p1++]);
else printf("%d ",b[p2++]);
}
}
return ;
}