bzoj2806 sam dp

bzoj2806.cpp

#include <cstdio>
#include <cstring>
#include <algorithm>
const int N = 1100000 * 2 + 9;
int fa[N],l[N],ch[N][3],len,last,cnt;
int f[N],q[N],n,m,a[N];
char s[N];
void add(int c)
{
    int np = ++cnt,p = last; last = np;
    l[np] = ++len;
    for (; p && !ch[p][c]; p = fa[p]) ch[p][c] = np;
    if (!p) fa[np] = 1;
    else {
        int q = ch[p][c];
        if (l[q] == l[p] + 1) fa[np] = q;
        else {
            int nq = ++cnt;
            memcpy(ch[nq],ch[q],sizeof ch[q]);
            fa[nq] = fa[q];
            l[nq] = l[p] + 1;
            fa[np] = fa[q] = nq;
            for (; ch[p][c] == q; p = fa[p]) ch[p][c] = nq;
        }
    }
}
bool check(char *s,int mid)
{
    f[0] = 0;
    int h = 1,t = 0,i;
    for (i = 1; *s; ++i,++s) {
        f[i] = f[i - 1];
        if (i - mid >= 0) {
            while (h <= t && f[q[t]] - q[t] <= f[i - mid] - (i - mid)) --t;
            q[++t] = i - mid;
        }
        while (h <= t && q[h] + a[i] < i) ++h;
        if (h <= t) f[i] = std::max(f[i],f[q[h]] + i - q[h]);
    }
    return f[i - 1] - (i - 1) * 0.9 >= -1e-6;
}
void init(char *s)
{
    for (int i = 1,len = 0,p = 1; *s; ++i,++s) {
        int c = *s - '0';
        while (p && !ch[p][c]) p = fa[p];
        if (!p) len = 0,p = 1;
        else {
            len = std::min(len,l[p]) + 1;
            p = ch[p][c];
        }
        a[i] = len;
    }
}
int work(char *s)
{
    init(s);
    int l = 0,r = len + 1;
    while (l + 1 < r) {
        int mid = (l + r) / 2;
        if (check(s,mid)) l = mid;
        else r = mid;
    }
    return l;
}
int main()
{
    #ifndef ONLINE_JUDGE
    freopen("2806.in","r",stdin);
    freopen("2806.out","w",stdout);
    #endif
    last = cnt = 1; len = 0;
    scanf("%d%d\n",&n,&m);
    while (m--) {
        scanf("%s\n",s);
        for (char *c = s; *c; ++c) add(*c - '0');
        add(2);
    }
    while (n--) {
        scanf("%s\n",s);
        printf("%d\n",work(s));
    }
}