BZOJ-2806: [Ctsc2012]Cheat

Description

对于每一位，求出向前能匹配子串的最长长度，广义sam，顺次匹配每一位，如果失配，则跳到其pre的位置继续进行匹配。
二分L，DP check即可。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 1101000 
int n,m;
char st[N];
int last=1,tot=1,ch[N<<1][2],dep[N<<1],pre[N<<1];
int f[N],q[N],d[N];
void insert(int x)
{
    int p=last;
    if(ch[p][x])
    {
        int q=ch[p][x];
        if(dep[q]==dep[p]+1) last=q;
        else
        {
            int clo=++tot; last=clo;
            memcpy(ch[clo],ch[q],sizeof(ch[q]));
            dep[clo]=dep[p]+1,pre[clo]=pre[q],pre[q]=clo;
            for(;p&&ch[p][x]==q;p=pre[p]) ch[p][x]=clo;
        }
    }
    else
    {
        int cur=++tot; last=cur; dep[cur]=dep[p]+1;
        for(;p&&!ch[p][x];p=pre[p]) ch[p][x]=cur;
        if(!p) pre[cur]=1;
        else
        {
            int q=ch[p][x];
            if(dep[q]==dep[p]+1) pre[cur]=q;
            else
            {
                int clo=++tot;
                memcpy(ch[clo],ch[q],sizeof(ch[q]));
                dep[clo]=dep[p]+1,pre[clo]=pre[q],pre[q]=pre[cur]=clo;
                for(;p&&ch[p][x]==q;p=pre[p]) ch[p][x]=clo;
            }
        }
    }
}
bool check(int x)
{
    if(!x) return true;
    int len=strlen(st+1),i,l=1,r=0; f[0]=0;
    for(i=1;i<=len;++i)
    {
        while(l<=r&&q[l]<i-d[i]) ++l;
        if(l<=r) f[i]=max(f[i-1],f[q[l]]-q[l]+i);
        else f[i]=f[i-1];
        if(i-x+1>=0)
        {
            while(l<=r&&f[q[r]]-q[r]<=f[i-x+1]-(i-x+1)) --r;
            q[++r]=i-x+1;
        }
    }
    return f[len]*10>=len*9;
}
int main()
{
    scanf("%d%d",&n,&m);
    while(m--)
    {
        scanf("%s",st);
        int len=strlen(st);
        last=1;
        for(int i=0;i<len;++i) insert(st[i]-'0');
    }
    while(n--)
    {
        scanf("%s",st+1);
        int len=strlen(st+1),p=1,i=1,now=0;
        while(i<=len)
        {
            if(ch[p][st[i]-'0'])
                d[i]=++now,p=ch[p][st[i]-'0'],++i;
            else if(p==1) now=d[i]=0,++i;
            else p=pre[p],now=dep[p];
        }
        // for(int i=0;i<=len;++i) printf("i= %d %d\n",i,check(i));
        int l=0,r=len+1,mid;
        while(l<r)
        {
            mid=(l+r)>>1;
            if(check(mid)) l=mid+1;
            else r=mid;
        }
        printf("%d\n",l-1);
    }
    return 0;
}