BZOJ3796: Mushroom追妹纸 后缀数组+二分+暴力
本题其实就是有限制的最长公共子串(注意\(s3\)那个限制千万别看反!!!)
于是乎本人无脑暴力,先求出后缀数组,二分的时候先在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; }
Sep 02, 2015 11:07:08 PM
大爷,在一个字符串里找另一个字符串出现的所有位置怎么做。。
Sep 04, 2015 08:57:08 AM
@ww140142: 才反应过来,不要叫我大爷。。。我哪够资格被称为“大爷”啊?
Oct 18, 2018 06:39:07 PM
its china language I know it
Oct 18, 2018 06:40:05 PM
maybe post is language category
Oct 18, 2018 06:41:09 PM
WordPress coding system
Oct 18, 2018 06:41:46 PM
nice articel
Oct 18, 2018 06:42:34 PM
Thank you for share good info
Dec 08, 2019 05:41:57 PM
Good coding system
Jan 06, 2021 06:17:16 PM
Keep up the good work , I read few posts on this web site and I conceive that your blog is very interesting and has sets of fantastic information. Cookie Boxes
Jan 27, 2021 05:07:52 PM
Keep up the good work , I read few posts on this web site and I conceive that your blog is very interesting and has sets of fantastic information. custom boxes with logo
Jan 28, 2021 03:38:27 PM
I might suggest solely beneficial in addition to trusted facts, and so find it: kw
Feb 09, 2021 04:07:48 PM
I simply want to tell you that I am new to weblog and definitely liked this blog site. Very likely I’m going to bookmark your blog . You absolutely have wonderful stories. Cheers for sharing with us your blog. 부스타빗
Feb 21, 2021 01:31:20 AM
this is an informative post and it is very useful and knowledgeable. therefore, I would like to thank you for the efforts you have made in writing this article.<br>
<br>
<a href="https://pagalstatus.com">Whatsapp Status Video</a><br>
<a href="https://pagalstatus.com/good-morning-wishes-status-videos.html">Good Morning Status Video Download</a><br>
<a href="https://pagalstatus.com/560-good-night-status-video.html">Good Night Status Video Download</a><br>
<a href="https://pagalstatus.com/category/whatsapp-status">New Status Video Download</a><br>
<a href="https://pagalstatus.com/category/sad-status">Sad Status Video Download</a><br>
<a href="https://pagalstatus.com/category/love-status">Love Status Video Download</a>
<a href="https://pagalstatus.com/happy-new-year-2021-status-video.html">Happy New Year 2021 Whatsapp Status Video Download
</a><br><a href="https://pagalstatus.com/happy-diwali-2020-status-video.html">Happy Diwali 2020 Whatsapp Status Video</a><br>
<a href="https://pagalstatus.com/merry-christmas-2020-status-video.html">Merry Christmas 2020 Whatsapp Status Video Downlaod</a><br><a href="https://pagalstatus.com/friendship-day-2020-whatsapp-status-video.html">Friendship Day 2020 Whatsapp Status Video Downlaod</a><br><a href="https://pagalstatus.com/category/day-wishes-status">Day Wishes Whatsapp Status Video</a>