CTSC2012 熟悉的文章 广义后缀自动机_单调队列

没啥难的，主要是单调队列忘了咋求了QAQ...

Code:

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <deque>

#define setIO(s) freopen(s".in","r",stdin)

#define maxn 2200000+10

#define  N 2

using namespace std;

char str[maxn],ss[maxn];

int str_len,ss_len,n,m,que[maxn];

int tot,last,dis[maxn],f[maxn],ch[maxn][N],mx[maxn],F[maxn];

void init(){last=tot=1; }

void ins(int c){

    int p=last,np=++tot; last=np,dis[np]=dis[p]+1;

    while(p&&!ch[p][c]) ch[p][c]=np,p=f[p];

    if(!p) f[np]=1;

    else {

        int q=ch[p][c];

        if(dis[q]==dis[p]+1) f[np]=q;

        else{

            int nq=++tot;

            dis[nq]=dis[p]+1;

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

            f[nq]=f[q],f[np]=f[q]=nq;

            while(p&&ch[p][c]==q) ch[p][c]=nq,p=f[p];

        }

    }

}

int check(int len){

    int hd=1,tl=0;

    for(int i=1;i<=len;++i) F[i]=0;

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

        int j=i-len;

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

        que[++tl]=j;

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

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

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

    }

    if(10*F[str_len]>=9*str_len) return 1;

    return 0;

}

void solve(){

    scanf("%s",str+1),str_len=strlen(str+1);

    int p=1,cur=0;

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

        int c=str[i]-'0';

        while(p && !ch[p][c]) p=f[p],cur=dis[p];

        if(!p) {p=1,cur=0;}

        else p=ch[p][c],cur+=1;

        mx[i]=cur;

    }

    int l=1,r=str_len,ans=0;

    while(l<=r){

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

        if(check(mid)) { ans=mid,l=mid+1;  }

        else r=mid-1;

    }

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

}

int main(){

    //setIO("input");

    scanf("%d%d",&n,&m),init();

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

    {

        scanf("%s",ss+1),ss_len=strlen(ss+1),last=1;

        for(int j=1;j<=ss_len;++j) ins(ss[j]-'0');

    }

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

    return 0;

}