BZOJ 2806 [Ctsc2012]Cheat (后缀自动机+二分+单调队列+dp)

题目大意：

给你一堆模式串和文本串

对于每个文本串，我们可以把它不可重叠地拆分成很多子串，如果拆分出的串作为子串出现在了任何一个模式串中，我们称它是“眼熟的”，我们必须保证“眼熟的”子串总长度不小于文本串的90%，现在定义一个数$L$，表示拆分出的子串的最小长度，求每个文本串的$L$的最大值

神题

考虑$L$的性质，发现$L$越大，“眼熟的子串”总长度越长

可以这样简单证明，长度越小的串，对于匹配越有利，因为如果一个大串出现在了模式串中，那么它的所有子串一定出现在了模式串中，反之，小串出现在模式串中，几个小串组成的大串却不一定出现在模式串中。

发现了这个性质，我们可以就二分$L$了

每次选择一个长度$L$作为每次拆分出的串的长度下限进行验证

定义$f[i]$表示拆分串$S[1,i]$，拆分出的一些串能在模式串中被识别，这些能被识别的串的最长长度

要么第i位单独被拆出来，并且不被识别，$f[i]=f[i-1]$

要么第i位作为末尾，组成一个能被识别的串，必须保证开头的前一位$j\in[1,i-L]$,$f[i]=f[j]+i-j$

发现$f[i]=f[j]+i-j=(f[j]-j)+i$可以用单调队列优化

能被识别的串长度必须不小于$L$！

预处理，对所有模式串建广义$SAM$

每次把当前文本串放进去跑，预处理出以i为结尾的最长可识别串的长度$ma_{i}$

如果当前节点没有$trs[x][c]$，就要像$fail$树一样不断跳$pre$删掉一部分前缀，直到碰到一个节点有$trs[x][c]$

如果当前节点有$trs[x][c]$，就跳过去。

但现在我们先不能跳过去，因为$trs[x][c]$的信息我们还不知道

现在$dep_{x}$表示的并非当前串的长度，而是在$trs$图里表现的最长长度，由于每次沿$trs$指针移动，长度+1，所以$ma_{i}=min(ma_{i-1}+1,dep[x]+1)$

细节比较多，尤其是单调队列的地方

#include <cmath>

#include <vector>

#include <cstdio>

#include <cstring>

#include <algorithm>

#define N1 1105000

#define S1 (N1<<1)

#define T1 (N1<<2)

#define ll long long

#define uint unsigned int

#define rint register int

#define dd double

#define il inline

#define inf 0x3f3f3f3f

#define idx(X) (X-'0')

using namespace std;

int gint()

{

    int ret=,fh=;char c=getchar();

    while(c<''||c>''){if(c=='-')fh=-;c=getchar();}

    while(c>=''&&c<=''){ret=ret*+c-'';c=getchar();}

    return ret*fh;

}

int N,M,len;

char str[N1];

int ma[N1];

namespace SAM{

int trs[S1][],pre[S1],dep[S1],tot,la;

void init(){tot=la=;}

void reduct(){la=;}

void insert(int c)

{

    int p=la,np=++tot,q,nq;la=np;

    dep[np]=dep[p]+;

    for(;p&&!trs[p][c];p=pre[p]) trs[p][c]=np;

    if(!p) {pre[np]=;return;}

    q=trs[p][c];

    if(dep[q]==dep[p]+) pre[np]=q;

    else{

        pre[nq=++tot]=pre[q];

        pre[q]=pre[np]=nq;

        dep[nq]=dep[p]+;

        memcpy(trs[nq],trs[q],sizeof(trs[q]));

        for(;p&&trs[p][c]==q;p=pre[p]) trs[p][c]=nq;

    }

}

void get_ma()

{

    int x=,c;

    for(int i=;i<=len;i++)

    {

        c=idx(str[i]);

        for(;x&&!trs[x][c];x=pre[x]);

        if(!x){ma[i]=,x=;continue;}

        ma[i]=min(ma[i-]+,dep[x]+);

        x=trs[x][c];

    }

}

};

int que[N1],f[N1];

int check(int L)

{

    int i,j,hd=,tl=;

    que[++tl]=;

    for(i=;i<L;i++) f[i]=;

    for(i=max(,L);i<=len;i++)

    {

        j=i-L;

        while(hd<=tl&&f[que[tl]]-que[tl]<=f[j]-j) tl--;

        que[++tl]=j;

        while(hd<=tl&&que[hd]<i-ma[i]) hd++;

        if(hd>tl) f[i]=f[i-];

        else f[i]=max(f[i-],f[que[hd]]+i-que[hd]);

    }

    if(*f[len]>=*len) return ;

    else return ;

}

int main()

{

    scanf("%d%d",&N,&M);

    int i,j,l,r,n,m,mid,mxl=,ans;

    SAM::init();

    for(m=;m<=M;m++)

    {

        scanf("%s",str+);

        len=strlen(str+);

        mxl=max(mxl,len);

        for(i=;i<=len;i++)

            SAM::insert(idx(str[i]));

        SAM::reduct();

    }

    for(n=;n<=N;n++)

    {

        scanf("%s",str+);

        len=strlen(str+);

        SAM::get_ma();

        l=,r=min(len,mxl),ans=;

        while(l<=r){

            mid=(l+r)>>;

            if(check(mid)) ans=mid,l=mid+;

            else r=mid-;

        }

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

    }

    return ;

}

巴特西

BZOJ 2806 [Ctsc2012]Cheat (后缀自动机+二分+单调队列+dp)

最新文章

热门文章