[BZOJ 3796]Mushroom追妹纸
题目
Mushroom最近看上了一个漂亮妹纸。他选择一种非常经典的手段来表达自己的心意——写情书。考虑到自己的表达能力，Mushroom决定不手写情书。他从网上找到了两篇极佳的情书，打算选择其*同的部分。另外，Mushroom还有个一个情敌Ertanis，此人也写了封情书给妹子。Mushroom不希望自己的情书中完整的出现了情敌的情书。（这样抄袭的事情就暴露了）。Mushroom把两封情书分别用字符串s1和s2来表示，Ertanis的情书用字符串s3来表示，他要截取的部分用字符串w表示。需满足：1、w是s1的子串2、w是s2的子串3、s3不是w的子串4、w的长度应尽可能大所谓子串是指：在字符串中连续的一段INPUT
输入文件为girl.in输入有三行，第一行为一个字符串s1第二行为一个字符串s2，第三行为一个字符串s3。输入仅含小写字母，字符中间不含空格。OUTPUT
输出文件为girl.out输出仅有一行，为w的最大可能长度，如w不存在，则输出0。SAMPLE
INPUT
abcdefabcfbcOUTPUT
2
解题报告
我不会说我一开始看错题废了我一个来小时的= =
首先我们可以把$s1$和$s2$中间加一个不会出现在该字符集中的字符将它俩接在一起，这个字符日常作用是分隔俩字符串
然后，我们对组合得到的字符串与$s3$跑$KMP$处理出每个匹配的串的位置
接下来就是极其简单的最长公共字串问题了，只要在判断时加一个是否被$KMP$标记过的条件即可
一定要读对题啊啊啊
s3不是w的子串！！！
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
char ch[][];
int len[],bl[];
char ran[]={'!','@','#','$'};
char s[];
int n,m;
int t1[],t2[],t3[],buc[];
int sa[],rank[],height[];
int kp[];
bool km[];
inline void get_kp(){
kp[]=-;
int i(),j(-);
while(i<len[]){
while(j!=-&&ch[][i]!=ch[][j])
j=kp[j];
kp[++i]=++j;
}
}
inline void kmp(){
int i(),j();
while(i<=n){
while(j!=-&&s[i]!=ch[][j])
j=kp[j];
++i,++j;
if(j==len[])
km[i-len[]]=;
}
}
inline void Suffix(){
int i,j,k(),p(),*x(t1),*y(t2),*t;
for(i=;i<=m;++i)buc[i]=;
for(i=;i<=n;++i)++buc[x[i]=s[i]];
for(i=;i<=m;++i)buc[i]+=buc[i-];
for(i=n;i>=;--i)sa[buc[x[i]]--]=i;
for(j=;p<n;j<<=,m=p){
for(p=,i=n-j+;i<=n;++i)y[++p]=i;
for(i=;i<=n;++i)
if(sa[i]>j)
y[++p]=sa[i]-j;
for(i=;i<=m;++i)buc[i]=;
for(i=;i<=n;++i)t3[i]=x[y[i]];
for(i=;i<=n;++i)++buc[t3[i]];
for(i=;i<=m;++i)buc[i]+=buc[i-];
for(i=n;i>=;--i)sa[buc[t3[i]]--]=y[i];
for(t=x,x=y,y=t,x[sa[]]=,p=,i=;i<=n;++i)
x[sa[i]]=((y[sa[i]]==y[sa[i-]])&&(y[sa[i]+j]==y[sa[i-]+j]))?p:++p;
}
for(i=;i<=n;++i)rank[sa[i]]=i;
for(i=;i<=n;height[rank[i++]]=k)
for(k?k--:,j=sa[rank[i]-];s[i+k]==s[j+k];++k);
}
inline bool judge(int po,int x){//cout<<l<<' '<<r<<' '<<x<<endl;
if(x<len[])
return true;
for(int i=po,j=;j<=x;++i,++j){
if(km[i]&&j+len[]-<=x)
return false;
}
return true;
}
inline bool check(int x){//cout<<x<<endl;
int i,j,k;
bool flag[];
for(i=;i<=n;++i){//cout<<i<<" "<<height[i]<<endl;
if(height[i]>=x){//cout<<endl;
for(j=i;height[j]>=x&&j<=n;++j);
--j;
// if(i==j)
// continue;
// cout<<i<<" "<<j<<endl<<endl;
memset(flag,,sizeof(flag));
for(k=i-;k<=j;++k)
flag[bl[sa[k]]]=;
if(flag[]&&flag[]&&judge(sa[i-],x))
return true;
// for(k=1;flag[k]&&k<=3;++k);
// if(k==3)
// return true;
i=j;
}
}
return false;
}
int main(){
scanf("%s%s%s",ch[],ch[],ch[]);
for(int i=;i<=;++i)
len[i]=strlen(ch[i]);
for(int i=;i<=;++i){
for(int j=;j<len[i];++j){
s[++n]=ch[i][j];
bl[n]=i;//cout<<n<<' '<<bl[n]<<endl;
}
s[++n]=ran[i];
}
get_kp();
kmp();
m=;
Suffix();
int l(),r(max(len[],len[])),ans();
while(l<=r){
int mid((l+r)>>);
if(check(mid))
ans=mid,l=mid+;
else
r=mid-;
}
printf("%d",ans);
}