题目描述

Description

Mushroom最近看上了一个漂亮妹纸。他选择一种非常经典的手段来表达自己的心意——写情书。考虑到自己的表达能力，Mushroom决定不手写情书。他从网上找到了两篇极佳的情书，打算选择其中共同的部分。另外，Mushroom还有个一个情敌Ertanis，此人也写了封情书给妹子。
Mushroom不希望自己的情书中完整的出现了情敌的情书。（这样抄袭的事情就暴露了）。
Mushroom把两封情书分别用字符串s1和s2来表示，Ertanis的情书用字符串s3来表示，他要截取的部分用字符串w表示。
需满足：
1、w是s1的子串
2、w是s2的子串
3、s3不是w的子串
4、w的长度应尽可能大
所谓子串是指：在字符串中连续的一段

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

题目分析

先用kmp标记s3在s1出现的每个位置 然后二分s2长度+hash

#include <cstdio>
#include <cstring>
#include <set>
#include <map>
#include <vector>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
char s1[50010],s2[50010],s3[50010];
int len1,len2,len3,tot;
int net[50010];
struct your
{
    int x,y;
}a[50010];
void getnext()
{
    int j=0,k=-1;
    net[0]=-1;
    while(j<len3)
    {
        if(k==-1||s3[j]==s3[k]) net[++j]=++k;
        else k=net[k];
    }
}
void kmp()
{
    int i=0,j=0;
    while(i<len1)
    {
        if(j==-1||s1[i]==s3[j]) i++,j++;
        else j=net[j];
        if(j==len3)  a[++tot].x=i-len3,a[tot].y=i-1,j=net[j];
    }
}
int cmp(your j,your k)
{
    return j.x<k.x;
}
map<long long,int>m;
long long seed=131,p=1000000009;
long long po[50100];
void init()
{
    po[0]=1;
    for(int i=1;i<=50000;i++) po[i]=po[i-1]*seed%p;
}
void get_hash(int mid)
{
    m.clear();
    long long tmp=0; 
    for(int i=1;i<=mid;i++) tmp=(tmp*seed+s2[i-1]-'a')%p;
    for(int i=mid;i<=len2;i++)
        m[tmp]=1,tmp=(((tmp-po[mid-1]*(s2[i-mid]-'a')%p+p)%p)*seed+(s2[i]-'a'))%p;
}
int num;
int ask(int x,int y)
{
    while(num<=tot&&a[num].x<x) num++;
    if(num>tot) return 1;
    if(a[num].y<=y) return 0;
    return 1;
}
int check(int mid)
{
    get_hash(mid);
    long long tmp=0;
    num=1;
    for(int i=1;i<=mid;i++) tmp=(tmp*seed+s1[i-1]-'a')%p;
    for(int i=mid;i<=len1;i++)
    {
        if(m[tmp]&&ask(i-mid,i-1)) return 1;
        tmp=(((tmp-po[mid-1]*(s1[i-mid]-'a')%p+p)%p)*seed+(s1[i]-'a'))%p;
    }
    return 0;
}
int main()
{
    scanf("%s%s%s",s1,s2,s3); 
    len1=strlen(s1),len2=strlen(s2),len3=strlen(s3);  
    getnext(),kmp();  
    sort(a+1,a+tot+1,cmp);
    init();
    int l=0,r=min(len2,len1),mid,ans=0;
    while(l<=r)
    {
        mid=(l+r)>>1;
        if(check(mid)) ans=max(ans,mid),l=mid+1;
        else r=mid-1;
    }
    printf("%d",ans);
    return 0;
}