【bzoj3796】Mushroom追妹纸 hash/sa+kmp+二分

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

1<=s1、s2的长度<=50000,1<=s3的长度<=10000

Sol

首先我们考虑没有限制3该怎么做，那当然是二分+hash裸题啦，每次只要二分串的长度mid，然后利用hash在\(O(n)\)时间内判断A，B中有没有相等的长度为mid的串，复杂度\(O(nlogn)\)。

然后如果加入限制3，那么代表我们选择的串里面不能包含串C，解决方法是对于AB串都跑一遍kmp（直接用hash暴力也行）找到所有C串出现的位置，打上标记，之后前缀和加一下。因为二分检验的本质是暴力，所以枚举所有定长子串的时候直接利用前缀和判断即可。具体地，对于AB串中出现C的每个起始位置++，前缀和之后，如果要判断l,r之间有没有串c，只要判断s[ed-lenc+1]-s[st-1]等不等于0即可。

时间复杂度仍然是\(O(nlogn)\)。

这里如果用map的话，复杂度多一个log（懒，最后卡过去了

似乎要卡单哈希？

sa+kmp的做法由于代码量比这个大就没写（逃，

sa把两个串拼一起做，然后依然kmp+前缀和，之后用height更新答案，二分找最靠前的C串出现位置，不断更新答案。

Code

#include <bits/stdc++.h>

using namespace std;

char a[100005],b[100005],c[20005];

int ans,la,lb,lc,nex[20005],s1[100005],s2[100005],h1[100005],h2[100005],bs[100005],P=233333333,h3[100005],h4[100005],as[100005];

map<int,int>mmpa,mmpb;

void getnex()

{

    nex[0]=-1;int i=0,j=-1;

    while(i<lc) if(j==-1||c[i]==c[j]) nex[++i]=++j;else j=nex[j];

}

void kmp(char *g,int *s,int len)

{

    for(int i=0,j=0;i<len;)

    {

        if(j==-1||g[i]==c[j]) i++,j++;else j=nex[j];

        if(j==lc) s[i-lc]++,j=nex[j];

    }

    for(int i=1;i<len;i++) s[i]+=s[i-1];

}

bool chk(int mid)

{

    mmpa.clear();mmpb.clear();

    for(int i=0;i<=la-mid;i++)

    {

        int st=i,ed=i+mid-1;

        if(mid>=lc&&s1[ed-lc+1]-(!st?0:s1[st-1])>0) continue;

        int tmp=h1[ed]-1ll*h1[st-1]*bs[mid]%P;tmp=(tmp+P)%P;

        int emp=h3[ed]-1ll*h3[st-1]*as[mid]%P;emp=(emp+P)%P;

        mmpa[tmp]=1;mmpb[emp]=1;

    }

    for(int i=0;i<=lb-mid;i++)

    {

        int st=i,ed=i+mid-1;

        if(mid>=lc&&s2[ed-lc+1]-(!st?0:s2[st-1])>0) continue;

        int tmp=h2[ed]-1ll*h2[st-1]*bs[mid]%P;tmp=(tmp+P)%P;

        int emp=h4[ed]-1ll*h4[st-1]*as[mid]%P;emp=(emp+P)%P;

        if(mmpa[tmp]&&mmpb[emp]) return 1;

    }

    return 0;

}

int main()

{

    scanf("%s%s%s",a,b,c),la=strlen(a),lb=strlen(b),lc=strlen(c);

    bs[0]=1;for(int i=1;i<=100000;i++) bs[i]=1ll*bs[i-1]*1926%P;

    as[0]=1;for(int i=1;i<=100000;i++) as[i]=1ll*as[i-1]*817%P;

    h1[0]=a[0]-'a'+1;for(int i=1;i<la;i++) h1[i]=(1ll*h1[i-1]*bs[1]+a[i]-'a'+1)%P;

    h2[0]=b[0]-'a'+1;for(int i=1;i<lb;i++) h2[i]=(1ll*h2[i-1]*bs[1]+b[i]-'a'+1)%P;

    h3[0]=a[0]-'a'+1;for(int i=1;i<la;i++) h3[i]=(1ll*h3[i-1]*as[1]+a[i]-'a'+1)%P;

    h4[0]=b[0]-'a'+1;for(int i=1;i<lb;i++) h4[i]=(1ll*h4[i-1]*as[1]+b[i]-'a'+1)%P;

    getnex();kmp(a,s1,la);kmp(b,s2,lb);

    for(int l=1,r=min(la,lb);l<=r;)

    {

        int mid=(l+r)>>1;

        if(chk(mid)) ans=mid,l=mid+1;

        else r=mid-1;

    }

    printf("%d\n",ans);

}

巴特西