[CTSC2012]熟悉的文章 （后缀自动机 单调队列）

/*
首先答案显然是具有单调性的， 所以可以二分进行判断

然后当我们二分过后考虑dp来求最长匹配个数， 发现每个点能够转移的地点 肯定是一段区间， 然后这样就能够得到一个log^2算法
至于每个点的匹配最长区间， 我们可以预处理出所有地点的最长匹配串

然后发现这个东西可以进行单调栈优化， 原因是往后能往前最大匹配到的点是不会超过前面的， 否则前面那个也会更长

然后就能快乐地一个log了


*/
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<iostream>
#define ll long long
#define M 2800010
#define mmp make_pair
using namespace std;
int read() {
    int nm = 0, f = 1;
    char c = getchar();
    for(; !isdigit(c); c = getchar()) if(c == '-') f = -1;
    for(; isdigit(c); c = getchar()) nm = nm * 10 + c - '0';
    return nm * f;
}
char s[M];
int ch[M][2], cnt = 1, lst = 1, fa[M], len[M], n, m;

void insert(int c) {
    int p = ++cnt, f = lst;
    lst = p;
    len[p] = len[f] + 1;
    while(f && !ch[f][c]) ch[f][c] = p, f = fa[f];
    if(f == 0) {
        fa[p] = 1;
    } else {
        int q = ch[f][c];
        if(len[q] == len[f] + 1) {
            fa[p] = q;
        } else {
            int nq = ++cnt;
            memcpy(ch[nq], ch[q], sizeof(ch[q]));
            fa[nq] = fa[q];
            len[nq] = len[f] + 1;
            fa[p] = fa[q] = nq;
            while(f && ch[f][c] == q) ch[f][c] = nq, f = fa[f];
        }
    }
}
int q[M], h, t, pre[M], f[M];
bool check(int k) {
    int l = strlen(s + 1);
    h = 1, t = 0;
    for(int i = 1; i <= l; i++) {
        f[i] = f[i - 1];
        if(i < k) continue;
        while(h <= t && f[q[t]] - q[t] <= f[i - k] - i + k) t--;
        q[++t] = i - k;
        while(h <= t && q[h] < i - pre[i]) h++;
        if(h <= t) f[i] = max(f[i], f[q[h]] + i - q[h]);
    }
    return f[l] * 10 >= l * 9;
}

void getpre() {
    int up = strlen(s + 1), now =  1, lenn = 0;
    for(int i = 1; i <= up; i++) {
        int c = s[i] - '0';

        while(now && !ch[now][c]) now = fa[now], lenn = len[now];
        if(!now) now = 1, lenn = 0;
        else now = ch[now][c], lenn++;

        pre[i] = lenn;
    }
}

int work() {
    getpre();
    int l = 1, r = strlen(s + 1);
    while(l + 1 < r) {
        int mid = (l + r) >> 1;
        if(check(mid)) l = mid;
        else r = mid;
    }
    if(!check(l)) return -1;
    if(check(r)) return r;
    return l;
}

int main() {
    n = read(), m = read();
    for(int i = 1; i <= m; i++) {
        lst = 1;
        scanf("%s", s + 1);
        int l = strlen(s + 1);
        for(int j = 1; j <= l; j++) insert(s[j] - '0');
    }
    while(n--) {
        scanf("%s", s + 1);
        cout << work() << "\n";
    }
    return 0;
}

[CTSC2012]熟悉的文章 （后缀自动机 单调队列）

原文：https://www.cnblogs.com/luoyibujue/p/10685328.html