bzoj3796 mushroom追妹子

bzoj3796 mushroom追妹子

​​Description Mushroom最近看上了一个漂亮妹纸。他选择一种非常经典的手段来表达自己的心意——写情书。考虑到自己的表达能力，Mushroom决定不手写情书。他从网上找到了两篇极佳的情书，打算选择其中共同的部分。另外，Mushroom还有个一个情敌Ertanis，此人也写了封情书给妹子。 Mushroom不希望自己的情书中完整的出现了情敌的情书。（这样抄袭的事情就暴露了）。 Mushroom把两封情书分别用字符串s1和s2来表示，Ertanis的情书用字符串s3来表示，他要截取的部分用字符串w表示。 需满足： 1、w是s1的子串 2、w是s2的子串 3、s3不是w的子串 4、w的长度应尽可能大 所谓子串是指：在字符串中连续的一段 【输入】 输入文件为girl.in 输入有三行，第一行为一个字符串s1第二行为一个字符串s2， 第三行为一个字符串s3。输入仅含小写字母，字符中间不含空格。 【输出】 输出文件为girl.out 输出仅有一行，为w的最大可能长度，如w不存在，则输出0。 【输入样例】 abcdef abcf bc 【输出样例】 2 【样例解释】 s1和s2的公共子串有abc,ab,bc,a,b,c,f，其中abc,bc包含子串bc不合法，所以最长的合法子串为ab。 【数据规模】 对于30%的数据：1<=s1、s2、s3的长度<=500 对于60%的数据：1<=s1、s2、s3的长度<=5000 对于100%的数据：1<=s1、s2的长度<=50000,1<=s3的长度<=10000

Input 输入有三行，第一行为一个字符串s1第二行为一个字符串s2， 第三行为一个字符串s3。输入仅含小写字母，字符中间不含空格。

Output 输出仅有一行，为w的最大可能长度，如w不存在，则输出0。

Sample Input abcdef

abcf

bc

Sample Output 2

【样例解释】

s1和s2的公共子串有abc,ab,bc,a,b,c,f，其中abc,bc包含子串bc不合法，所以最长的合法子串为ab。

HINT

对于100%的数据：1<=s1、s2的长度<=50000,1<=s3的长度<=10000

题意要求我们找一个串1&串2完整包含的子串，并且串3不完整在他们里面

首先我们需要制作一个L数组表示L[i] 表示 从L[i]->i这个区间完整包含了s3并且这个区间的长度最小

如何制作L数组我们可以用kmp去匹配

然后二分验证答案是否正确 中间有分隔符，不要忘记处理

#include#include#define N 110000int n;char s[N>>1],t[N>>1];int a[N],len[5],rank[N<<1],rank1[N],height[N],tmp[N],sa[N],count[N],L[N],bl[N],next[N>>1];inline int max(int a,int b){ return a>b?a:b;}inline bool judge(int x){ bool f[3];f[1]=f[2]=false; for (int i=1;i<=n;++i){ if (height[i]>=x){ if(sa[i]<=L[sa[i]+x-1]) continue; f[bl[sa[i]]]=true; }else{ if (f[1]&&f[2]) return true; f[1]=f[2]=false; if (sa[i]<=L[sa[i]+x-1])continue; f[bl[sa[i]]]=true; } } return false;}int main(){ //freopen("bzoj3796.in","r",stdin); n=1;int l=1,r=0;int m=30; for (int i=1;i<=2;++i){ scanf("%s",s+1);len[i]=strlen(s+1); r=max(r,len[i]);for (int j=0;j=1;--i) tmp[count[rank[i+p]]--]=i; for (int i=1;i<=m;++i) count[i]=0; for (int i=1;i<=n;++i) count[rank[i]]++; for (int i=1;i<=m;++i) count[i]+=count[i-1]; for (int i=n;i>=1;--i) sa[count[rank[tmp[i]]]--]=tmp[i]; memcpy(rank1,rank,sizeof(rank)>>1); rank[sa[1]]=k=1; for (int i=2;i<=n;++i){ if (rank1[sa[i]+p]!=rank1[sa[i-1]+p]||rank1[sa[i]]!=rank1[sa[i-1]])++k; rank[sa[i]]=k; } } k=0; for (int i=1;i<=n;++i){ if (rank[i]==1) continue; k=k==0?0:k-1; while (a[i+k]==a[sa[rank[i]-1]+k])++k; height[rank[i]]=k; } //getnext next[1]=0; for (int i=2;i<=len[3];++i){ while (k&&t[k+1]!=t[i]) k=next[k]; if (t[k+1]==t[i])++k; next[i]=k; } // make Array L[] int last=0;k=0; for (int i=1;i<=len[2];++i){ while (k&&s[i]!=t[k+1]) k=next[k]; if (s[i]==t[k+1]) ++k; if (k==len[3]) last=len[1]+1+i-len[3]+1;//别忘记处理分隔符x L[len[1]+i+1]=last; } while (l<=r){ int mid=(l+r)>>1; if (judge(mid)) l=mid+1;else r=mid-1; } printf("%d",l-1); return 0; }

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。