【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
abcf
bc
Sample Output
2
【样例解释】
s1和s2的公共子串有abc,ab,bc,a,b,c,f，其中abc,bc包含子串bc不合法，所以最长的合法子串为ab。
【样例解释】
s1和s2的公共子串有abc,ab,bc,a,b,c,f，其中abc,bc包含子串bc不合法，所以最长的合法子串为ab。
HINT
对于100%的数据：1<=s1、s2的长度<=50000,1<=s3的长度<=10000
题解：“没有什么字符串问题是hash解决不了的。”
先用hash找出s3在s1中所有出现的位置，把这些位置都打上危险标记。显然答案是可二分的，于是二分答案。假设当前二分的答案为len，我们将s2中所有长度为len的子串的hash值都拿出来，扔到set里，我们再枚举s1中所有长度为len的子串，如果当前子串再set中出现过，并且当前串中不包含危险标记，则该串是符合要求的。
此外，望大家学习正确的重载运算符的姿势，并养成良好的习惯啊~（当你看见编译时反馈的一大坨信息你就洒sha了。）
#include <cstdio>
#include <cstring>
#include <iostream>
#include <set>
#include <utility>
using namespace std;
const int maxn=50010;
typedef long long ll;
const ll m1=998244353;
const ll m2=1000000007;
struct pll
{
ll F,S;
pll() {}
pll(ll a,ll b){F=a,S=b;}
pll operator * (const ll &b) const {return pll(F*b%m1,S*b%m2);}
pll operator + (const ll &b) const {return pll((F+b)%m1,(S+b)%m2);}
pll operator * (const pll &b) const {return pll(F*b.F%m1,S*b.S%m2);}
pll operator - (const pll &b) const {return pll((F-b.F+m1)%m1,(S-b.S+m2)%m2);}
bool operator < (const pll &b) const {return (F==b.F)?(S<b.S):(F<b.F);}
bool operator == (const pll &b) const {return F==b.F&&S==b.S;}
}h1[maxn],h2[maxn],h3,bs[maxn];
int l1,l2,l3;
char s1[maxn],s2[maxn],s3[maxn];
set<pll> s;
int dan[maxn];
bool solve(int l)
{
int i;
s.clear();
for(i=l;i<=l2;i++) s.insert(h2[i]-(h2[i-l]*bs[l]));
for(i=l;i<=l1;i++)
{
if((l<l3||!(dan[i]-dan[i-l+l3-1]))&&s.find(h1[i]-(h1[i-l]*bs[l]))!=s.end()) return 1;
}
return 0;
}
int main()
{
scanf("%s%s%s",s1,s2,s3),l1=strlen(s1),l2=strlen(s2),l3=strlen(s3);
int i;
for(bs[0]=pll(1,1),i=1;i<=max(l1,l2);i++) bs[i].F=bs[i-1].F*233%m1,bs[i].S=bs[i-1].S*233%m2;
for(i=1;i<=l1;i++) h1[i]=(h1[i-1]*233)+s1[i-1];
for(i=1;i<=l2;i++) h2[i]=(h2[i-1]*233)+s2[i-1];
for(i=1;i<=l3;i++) h3=(h3*233)+s3[i-1];
for(i=l3;i<=l1;i++) if(h1[i]-(h1[i-l3]*bs[l3])==h3) dan[i]=1;
for(i=1;i<=l1;i++) dan[i]+=dan[i-1];
int l=1,r=min(l1,l2)+1,mid;
while(l<r)
{
mid=(l+r)>>1;
if(solve(mid)) l=mid+1;
else r=mid;
}
printf("%d",l-1);
return 0;
}