8

BZOJ3796: Mushroom追妹纸 后缀数组+二分+暴力

 3 years ago
source link: http://wyfcyx.is-programmer.com/posts/73323.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

BZOJ3796: Mushroom追妹纸 后缀数组+二分+暴力

shinbokuow posted @ 6 年前 in BZOJ with tags 二分 后缀数组 , 4052 阅读

本题其实就是有限制的最长公共子串（注意s3s3那个限制千万别看反！！！）

于是乎本人无脑暴力，先求出后缀数组，二分的时候先在height连续块中暴力求一遍KMP,看一下这个串合不合适。

不会算严格的时间复杂度，不过貌似也不是特别慢。

（注：下面的DC3是有bug的，请不要无脑搬运）

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define N 110010
int v[N*3],sa[N*3],qa[N],qb[N],val[N];
inline void RadixSort(int*v,int*q,int*sa,int n,int m){
register int i,j;static int c[N];
for(i=0;i<m;++i)c[i]=0;
for(i=0;i<n;++i)++c[v[q[i]]];
for(i=1;i<m;++i)c[i]+=c[i-1];
for(i=n-1;i>=0;--i)sa[--c[v[q[i]]]]=q[i];
}
inline bool cmp1(int*v,int a,int b){
return v[a]==v[b]&&v[a+1]==v[b+1]&&v[a+2]==v[b+2];
}
inline bool cmp2(int d,int*v,int a,int b){
if(d==1)return v[a]<v[b]||(v[a]==v[b]&&val[a+1]<val[b+1]);
else return v[a]<v[b]||(v[a]==v[b]&&cmp2(1,v,a+1,b+1));
}
#define f(x) ((x)%3==1?(x)/3:na+(x)/3)
#define rf(x) ((x)<na?3*(x)+1:3*((x)-na)+2)
void dc3(int*v,int*sa,int n,int m){
int i,j,k,*nv=v+n+3,*nsa=sa+n+3,na=(n+2)/3,nbc=0,lab;
v[n]=v[n+1]=v[n+2]=0;
for(i=0;i<n;++i)if(i%3)qa[nbc++]=i;if(n%3==1)qa[nbc++]=n;
RadixSort(v+2,qa,qb,nbc,m);
RadixSort(v+1,qb,qa,nbc,m);
RadixSort(v,qa,qb,nbc,m);
for(lab=i=0;i<nbc;++lab,i=j+1){
for(j=i;j<nbc-1&&cmp1(v,qb[j],qb[j+1]);++j);
for(k=i;k<=j;++k)nv[f(qb[k])]=lab;
}
if(lab<nbc)dc3(nv,nsa,nbc,lab);
else for(i=0;i<nbc;++i)nsa[nv[i]]=i;
for(i=j=0;i<nbc;++i)if(nsa[i]<na)qb[j++]=3*nsa[i];
RadixSort(v,qb,qa,na,m);
for(i=0;i<nbc;++i)val[qb[i]=rf(nsa[i])]=i;
for(i=lab=0,j=(n%3==1);i<na&&j<nbc;)
sa[lab++]=cmp2(qb[j]%3,v,qa[i],qb[j])?qa[i++]:qb[j++];
while(i<na)sa[lab++]=qa[i++];
while(j<nbc)sa[lab++]=qb[j++];
}
int rk[N],h[N];
inline void work(int n){
register int i,j;
for(i=0;i<n;++i)rk[sa[i]]=i;
for(i=0;i<n;++i){
if(rk[i]){
j=0;if(i)j=max(0,h[rk[i-1]]-1);
while(i+j<n&&sa[rk[i]-1]+j<n&&v[i+j]==v[sa[rk[i]-1]+j])++j;
h[rk[i]]=j;
}
}
}
char s1[50010],s2[50010],s3[10010];int bel[N];
int pre[N];
//bool crashed1[50010],crashed2[50010];
int main(){
#ifndef ONLINE_JUDGE
freopen("tt.in","r",stdin);
#endif
register int i,j,k;
scanf("%s%s%s",s1,s2,s3+1);int l1=strlen(s1),l2=strlen(s2),l3=strlen(s3+1);
for(i=2,j=0;i<=l3;++i){for(;j&&s3[j+1]!=s3[i];j=pre[j]);if(s3[j+1]==s3[i])++j;pre[i]=j;}
/*for(i=j=0;i<l1;++i){
for(;j&&s3[j+1]!=s1[i];j=pre[j]);if(s3[j+1]==s1[i])++j;if(j==l3)crashed1[i]=1;
}
for(i=j=0;i<l2;++i){
for(;j&&s3[j+1]!=s2[i];j=pre[j]);if(s3[j+1]==s2[i])++j;if(j==l3)crashed2[i]=1;
}*/
int id=0;
for(i=0;i<l1;++i)v[id++]=s1[i],bel[id-1]=1;v[id++]='$';
for(i=0;i<l2;++i)v[id++]=s2[i],bel[id-1]=2;
dc3(v,sa,id,256);
work(id);
int L=0,R=min(l1,l2),mid;bool is[4];
while(L<R){
mid=(L+R+1)>>1;
bool ac=0;
for(i=1;i<id;){
if(h[i]>=mid){
int ins=sa[i];bool cannot=0;
for(k=0,j=ins;j<ins+mid;++j){
while(k&&s3[k+1]!=v[j])k=pre[k];if(s3[k+1]==v[j])++k;if(k==l3){cannot=1;break;}
}
is[0]=is[1]=is[2]=is[3]=0;
for(j=i;j+1<id&&h[j+1]>=mid;++j);
/*for(k=i-1;k<=j;++k){
if(sa[k]>=0&&sa[k]<=l1-1&&sa[k]+mid-1<l1&&crashed1[sa[k]+mid-1])cannot=1;
if(sa[k]>=l1+1&&sa[k]<=l1+l2&&sa[k]-l1-1+mid-1<l2&&crashed2[sa[k]-l1-1+mid-1])cannot=1;
}*/
if(!cannot){
is[bel[sa[i-1]]]=1;
for(k=i;k<=j;++k)is[bel[sa[k]]]=1;
if(is[1]&&is[2]&&!is[3]){ac=1;L=mid;break;}
}
i=j+1;
}else++i;
}
if(!ac)R=mid-1;
}
printf("%d",L);return 0;
}

report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK