验证中...
10月20日,北京【人工智能】源创会火热报名中,点击报名收获 AI 训练指南
【BZOJ4278】【ONTAK2015】Tasowanie
原始数据 复制代码
#include<bits/stdc++.h>
using namespace std;
const int N=400010;
int x[N],c[N],y[N],sa[N],rk[N];
int s[N];
void get_sa(int n,int m){
for(int i=1;i<=n;i++) c[x[i]=s[i]]++;
for(int i=2;i<=m;i++) c[i]+=c[i-1];
for(int i=n;i;i--) sa[c[x[i]]--]=i;
for(int k=1;k<=n;k<<=1){
int p=0;
for(int i=n-k+1;i<=n;i++) y[++p]=i;
for(int i=1;i<=n;i++) if(sa[i]>k) y[++p]=sa[i]-k;
for(int i=1;i<=m;i++) c[i]=0;
for(int i=1;i<=n;i++) c[x[i]]++;
for(int i=2;i<=m;i++) c[i]+=c[i-1];
for(int i=n;i;i--) sa[c[x[y[i]]]--]=y[i];
swap(x,y);
x[sa[1]]=1,p=1;
for(int i=2;i<=n;i++)
x[sa[i]]=(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k])?p:++p;
if(n==p) break;
m=p;
}
for(int i=1;i<=n;i++) rk[sa[i]]=i;
}
bool cmp(int a,int b){return s[a]==s[b]?rk[a]<rk[b]:s[a]<s[b];}
int main(){
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&s[i]);
s[1+n]=1001;
int m;
scanf("%d",&m);
for(int i=n+2;i<=n+m+1;i++) scanf("%d",&s[i]);
s[n+m+2]=1001;
get_sa(n+m+2,1001);
int i=1,j=n+2;
for(;;){
if(cmp(i,j)){
printf("%d ",s[i]);
i++;
}else{
printf("%d ",s[j]);
j++;
}
if(i>n||j>n+m+1) break;
}
for(;i<=n;i++) printf("%d ",s[i]);
for(;j<=n+m+1;j++) printf("%d ",s[j]);
return 0;
}

评论列表( 0 )

你可以在登录后,发表评论

搜索帮助