BZOJ 3796 后缀数组+KMP

思路：

写得我头脑发蒙,,, 旁边还有俩唱歌的 抓狂

（感谢lh大爷查错）

首先

1、w是s1的子串

2、w是s2的子串

这两步很好办啊~ 后缀数组一下O(n)就可以搞

重点是 这个：3、s3不是w的子串

怎么办呢

把 1、3做一发KMP

那么取一下min就好了

注意重叠的情况

（其实是可以O(n)搞的 我一开始写错了 改的时候偷懒就直接二分了）

也很快~

//By SiriusRen

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

const int N=100050;

int len1,len2,len3,n,cntA[N],cntB[N],A[N],B[N],sa[N],tsa[N],rk[N],ht[N],next[N],rec[N],ans;

char s[N],s1[N],s2[N],s3[N];

void SA(){

    for(int i=1;i<=n;i++)cntA[s[i]]++;

    for(int i=1;i<=256;i++)cntA[i]+=cntA[i-1];

    for(int i=n;i;i--)sa[cntA[s[i]]--]=i;

    rk[sa[1]]=1;

    for(int i=2;i<=n;i++)rk[sa[i]]=rk[sa[i-1]]+(s[sa[i]]!=s[sa[i-1]]);

    for(int l=1;rk[sa[n]]<n;l<<=1){

        memset(cntA,0,sizeof(cntA));

        memset(cntB,0,sizeof(cntB));

        for(int i=1;i<=n;i++)

            cntA[A[i]=rk[i]]++,

            cntB[B[i]=(i+l<=n?rk[i+l]:0)]++;

        for(int i=1;i<=n;i++)cntA[i]+=cntA[i-1],cntB[i]+=cntB[i-1];

        for(int i=n;i;i--)tsa[cntB[B[i]]--]=i;

        for(int i=n;i;i--)sa[cntA[A[tsa[i]]]--]=tsa[i];

        rk[sa[1]]=1;

        for(int i=2;i<=n;i++)rk[sa[i]]=rk[sa[i-1]]+(A[sa[i]]!=A[sa[i-1]]||B[sa[i]]!=B[sa[i-1]]);

    }

    for(int i=1,j=0;i<=n;i++){

        j=j?j-1:0;

        while(s[i+j]==s[sa[rk[i]-1]+j])j++;

        ht[rk[i]]=j;

    }

}

void get_next(){

    int j=0;next[1]=0;

    for(int i=2;s3[i];i++){

        while(j&&s3[i]!=s3[j+1])j=next[j];

        if(s3[i]==s3[j+1])j++;

        next[i]=j;

    }

}

void KMP(){

    int j=0;

    for(int i=1;i<=n;i++){

        while(j&&s[i]!=s3[j+1])j=next[j];

        if(s[i]==s3[j+1])j++;

        if(j==len3){rec[i]=i;j=next[j];}

    }

}

int main(){

    scanf("%s%s%s",s1+1,s2+1,s3+1);

    len1=strlen(s1+1),len2=strlen(s2+1),len3=strlen(s3+1);

    s[len1+1]='#';

    for(int i=1;i<=len1;i++)s[i]=s1[i];

    for(int i=1;i<=len2;i++)s[i+len1+1]=s2[i];

    n=len1+len2+1;

    SA();get_next();KMP();rec[n+2]=n+1;

    for(int i=n+2;i;i--)if(!rec[i-1])rec[i-1]=rec[i];

    for(int i=1;i<=n;i++){

        int maxx=max(sa[i],sa[i-1]),minn=min(sa[i],sa[i-1]);

        int tempmin=minn,tempmax=maxx;

        int tempx=*(lower_bound(rec+1,rec+2+n,len3-1+minn))-minn;

        int tempy=*(lower_bound(rec+1,rec+2+n,len3-1+maxx))-maxx;

        if(maxx>len1&&minn<=len1)ans=max(ans,min(ht[i],min(tempx,tempy)));

    }

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

}