BZOJ3796: Mushroom追妹纸 后缀数组+二分+暴力

本题其实就是有限制的最长公共子串（注意\(s3\)那个限制千万别看反！！！）

于是乎本人无脑暴力，先求出后缀数组，二分的时候先在height连续块中暴力求一遍KMP,看一下这个串合不合适。

不会算严格的时间复杂度，不过貌似也不是特别慢。

（注：下面的DC3是有bug的，请不要无脑搬运）

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
 
#define N 110010
int v[N*3],sa[N*3],qa[N],qb[N],val[N];
inline void RadixSort(int*v,int*q,int*sa,int n,int m){
    register int i,j;static int c[N];
    for(i=0;i<m;++i)c[i]=0;
    for(i=0;i<n;++i)++c[v[q[i]]];
    for(i=1;i<m;++i)c[i]+=c[i-1];
    for(i=n-1;i>=0;--i)sa[--c[v[q[i]]]]=q[i];
}
inline bool cmp1(int*v,int a,int b){
    return v[a]==v[b]&&v[a+1]==v[b+1]&&v[a+2]==v[b+2];
}
inline bool cmp2(int d,int*v,int a,int b){
    if(d==1)return v[a]<v[b]||(v[a]==v[b]&&val[a+1]<val[b+1]);
    else return v[a]<v[b]||(v[a]==v[b]&&cmp2(1,v,a+1,b+1));
}
#define f(x) ((x)%3==1?(x)/3:na+(x)/3)
#define rf(x) ((x)<na?3*(x)+1:3*((x)-na)+2)
void dc3(int*v,int*sa,int n,int m){
    int i,j,k,*nv=v+n+3,*nsa=sa+n+3,na=(n+2)/3,nbc=0,lab;
    v[n]=v[n+1]=v[n+2]=0;
    for(i=0;i<n;++i)if(i%3)qa[nbc++]=i;if(n%3==1)qa[nbc++]=n;
    RadixSort(v+2,qa,qb,nbc,m);
    RadixSort(v+1,qb,qa,nbc,m);
    RadixSort(v,qa,qb,nbc,m);
    for(lab=i=0;i<nbc;++lab,i=j+1){
        for(j=i;j<nbc-1&&cmp1(v,qb[j],qb[j+1]);++j);
        for(k=i;k<=j;++k)nv[f(qb[k])]=lab;
    }
    if(lab<nbc)dc3(nv,nsa,nbc,lab);
    else for(i=0;i<nbc;++i)nsa[nv[i]]=i;
    for(i=j=0;i<nbc;++i)if(nsa[i]<na)qb[j++]=3*nsa[i];
    RadixSort(v,qb,qa,na,m);
    for(i=0;i<nbc;++i)val[qb[i]=rf(nsa[i])]=i;
    for(i=lab=0,j=(n%3==1);i<na&&j<nbc;)
        sa[lab++]=cmp2(qb[j]%3,v,qa[i],qb[j])?qa[i++]:qb[j++];
    while(i<na)sa[lab++]=qa[i++];
    while(j<nbc)sa[lab++]=qb[j++];
}
int rk[N],h[N];
inline void work(int n){
    register int i,j;
    for(i=0;i<n;++i)rk[sa[i]]=i;
    for(i=0;i<n;++i){
        if(rk[i]){
            j=0;if(i)j=max(0,h[rk[i-1]]-1);
            while(i+j<n&&sa[rk[i]-1]+j<n&&v[i+j]==v[sa[rk[i]-1]+j])++j;
            h[rk[i]]=j;
        }
    }
}
char s1[50010],s2[50010],s3[10010];int bel[N];
 
int pre[N];
//bool crashed1[50010],crashed2[50010];
 
int main(){
    #ifndef ONLINE_JUDGE
    freopen("tt.in","r",stdin);
    #endif
    register int i,j,k;
 
    scanf("%s%s%s",s1,s2,s3+1);int l1=strlen(s1),l2=strlen(s2),l3=strlen(s3+1);
 
    for(i=2,j=0;i<=l3;++i){for(;j&&s3[j+1]!=s3[i];j=pre[j]);if(s3[j+1]==s3[i])++j;pre[i]=j;}
    /*for(i=j=0;i<l1;++i){
        for(;j&&s3[j+1]!=s1[i];j=pre[j]);if(s3[j+1]==s1[i])++j;if(j==l3)crashed1[i]=1;
    }
    for(i=j=0;i<l2;++i){
        for(;j&&s3[j+1]!=s2[i];j=pre[j]);if(s3[j+1]==s2[i])++j;if(j==l3)crashed2[i]=1;
    }*/
 
    int id=0;
    for(i=0;i<l1;++i)v[id++]=s1[i],bel[id-1]=1;v[id++]='$';
    for(i=0;i<l2;++i)v[id++]=s2[i],bel[id-1]=2;
     
 
    dc3(v,sa,id,256);
    work(id);
 
    int L=0,R=min(l1,l2),mid;bool is[4];
    while(L<R){
        mid=(L+R+1)>>1;
        bool ac=0;
        for(i=1;i<id;){
            if(h[i]>=mid){
                 
                int ins=sa[i];bool cannot=0;
                for(k=0,j=ins;j<ins+mid;++j){
                    while(k&&s3[k+1]!=v[j])k=pre[k];if(s3[k+1]==v[j])++k;if(k==l3){cannot=1;break;}
                }
                 
                is[0]=is[1]=is[2]=is[3]=0;
                for(j=i;j+1<id&&h[j+1]>=mid;++j);
                /*for(k=i-1;k<=j;++k){
                    if(sa[k]>=0&&sa[k]<=l1-1&&sa[k]+mid-1<l1&&crashed1[sa[k]+mid-1])cannot=1;
                    if(sa[k]>=l1+1&&sa[k]<=l1+l2&&sa[k]-l1-1+mid-1<l2&&crashed2[sa[k]-l1-1+mid-1])cannot=1;
                }*/
                if(!cannot){
                    is[bel[sa[i-1]]]=1;
                    for(k=i;k<=j;++k)is[bel[sa[k]]]=1;
                    if(is[1]&&is[2]&&!is[3]){ac=1;L=mid;break;}
                }
                i=j+1;
            }else++i;
        }
        if(!ac)R=mid-1;
    }
 
    printf("%d",L);return 0;
}