[文章目录]
Description
Mushroom最近看上了一个漂亮妹纸。Mushroom把两封情书分别用字符串s1和s2来表示，Ertanis的情书用字符串s3来表示，他要截取的部分用字符串w表示。需满足：
1、w是s1的子串
2、w是s2的子串
3、s3不是w的子串
4、w的长度应尽可能大
二分+hash。
将s1,s2中出现s3的位置标记。然后二分长度，判断是否有相同合法的子串。
#include <set>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef unsigned long long ull;
ull fl1,fl2;
int len1,len2,len3;
char s1[51000],s2[51000],s3[11000];
bool v1[51000],v2[51000];
ull pow(ull x,int y)
{
ull re=1;
while(y)
{
if(y&1) re=re*x;
x=x*x; y>>=1;
}
return re;
}
void make_fl()
{
ull hs1,hs2,po1=pow(233,len3-1),po2=pow(2333,len3-1);
if(len1>=len3)
{
hs1=hs2=0;
for(int i=0;i!=len3;++i)
hs1=hs1*233+s1[i],hs2=hs2*2333+s1[i];
if(hs1==fl1&&hs2==fl2) v1[len3-1]=1;
for(int i=len3;i!=len1;++i)
{
hs1-=po1*s1[i-len3]; hs2-=po2*s1[i-len3];
hs1=hs1*233+s1[i]; hs2=hs2*2333+s1[i];
if(hs1==fl1&&hs2==fl2) v1[i]=1;
}
}
if(len2>=len3)
{
hs1=hs2=0;
for(int i=0;i!=len3;++i)
hs1=hs1*233+s2[i],hs2=hs2*2333+s2[i];
if(hs1==fl1&&hs2==fl2) v2[len3-1]=1;
for(int i=len3;i!=len2;++i)
{
hs1-=po1*s2[i-len3]; hs2-=po2*s2[i-len3];
hs1=hs1*233+s2[i]; hs2=hs2*2333+s2[i];
if(hs1==fl1&&hs2==fl2) v2[i]=1;
}
}
}
struct node {ull a,b;};
bool operator<(node x,node y) {return x.a==y.a?x.b<y.b:x.a<y.a;}
set<node>s;
bool check(int x)
{
s.clear(); ull hs1=0,hs2=0; int num=0;
ull po1=pow(233,x-1),po2=pow(2333,x-1);
for(int i=0;i!=x;++i)
{
hs1=hs1*233+s1[i],hs2=hs2*2333+s1[i];
if(v1[i]) num++;
}
if(!num) s.insert((node){hs1,hs2});
for(int i=x;i!=len1;++i)
{
hs1-=po1*s1[i-x]; hs2-=po2*s1[i-x];
hs1=hs1*233+s1[i],hs2=hs2*2333+s1[i];
if(x>=len3&&v1[i]) num++;
if(x>=len3&&v1[i-x+len3-1]) num--;
if(!num) s.insert((node){hs1,hs2});
}
hs1=hs2=0; num=0;
for(int i=0;i!=x;++i)
{
hs1=hs1*233+s2[i],hs2=hs2*2333+s2[i];
if(v2[i]) num++;
}
if(!num&&s.find((node){hs1,hs2})!=s.end()) return 1;
for(int i=x;i!=len2;++i)
{
hs1-=po1*s2[i-x]; hs2-=po2*s2[i-x];
hs1=hs1*233+s2[i],hs2=hs2*2333+s2[i];
if(x>=len3&&v2[i]) num++;
if(x>=len3&&v2[i-x+len3-1]) num--;
if(!num&&s.find((node){hs1,hs2})!=s.end()) return 1;
}
return 0;
}
int main()
{
scanf("%s%s%s",s1,s2,s3);
len1=strlen(s1); len2=strlen(s2); len3=strlen(s3);
for(int i=0;i!=len3;++i)
fl1=fl1*233+s3[i],fl2=fl2*2333+s3[i];
make_fl(); int l=0,r=min(len1,len2)+1,mid;
while(l<r)
{
mid=(l+r)>>1;
if(check(mid)) l=mid+1;
else r=mid;
}
printf("%d",l-1);
return 0;
}