题目链接：Luogu 4022

阿米巴是小强的好朋友。

在小强眼中，阿米巴是一个作文成绩很高的文艺青年。为了获取考试作文的真谛，小强向阿米巴求教。阿米巴给小强展示了几篇作文，小强觉得这些文章怎么看怎么觉得熟悉，仿佛是某些范文拼拼凑凑而成的。小强不禁向阿米巴投去了疑惑的眼光，却发现阿米巴露出了一个狡黠的微笑。

为了有说服力地向阿米巴展示阿米巴的作文是多么让人觉得眼熟，小强想出了一个评定作文「熟悉程度」的量化指标：$L_0$。小强首先将作文转化成一个 $01$ 串。之后，小强搜集了各路名家的文章，同样分别转化成 $01$ 串后，整理出一个包含了 $m$ 个 $01$ 串的标准作文库。

小强认为：如果一个 $01$ 串长度不少于 $L$ 且在标准作文库中的某个串里出现过（即它是标准作文库 的某个串的一个连续子串），那么它是「熟悉」的。对于一篇作文 $A$，如果能够把 $A$ 分割成若干段子串，其中「熟悉」的子串的长度总和不少于 $A$ 总长度的 $90\%$，那么称 $A$ 是「熟悉的文章」。$L_0$ 是能够让 $A$ 成为「熟悉的文章」的所有 $L$ 的最大值。如果不存在这样的 $L$，那么规定 $L_0 = 0$。

现在小强有 $n$ 篇作文需要进行判断，请你分别求出他们的 $L_0$ 值。

数据范围：输入文件的长度不超过 $1.1 \times 10 ^ 6​$ 字节。

Solution

首先考虑二分 $L$ 的值，求出当前的 $L$ 下的「熟悉」的子串的总长度的最大值。

$$ f(i) = \max_{j = i - s_i} ^ {i - L}f(j) + i - j $$

其中 $s_i$ 表示以 $i$ 结束的字符串在标准作文库中出现的最长长度。可以直接对作文库建立广义 $\text{SAM}​$ 然后预处理出来。

发现 $i - s_i$ 一定是单调不降的，$i - L$ 一定是单调递增的，可以使用单调队列维护 $f(j) - j$，可以优化掉一个 $\mathcal O(n)$ 的复杂度。

时间复杂度：$\mathcal O(n \log n)$。

Code

#include <cstdio>
#include <cstring>
#include <algorithm>

const int N = 1.1e6 + 5;

int n, m, f[N], p[N], q[N];
char s[N];

template <int MAX, int S>
struct SAM {
    static const int N = MAX << 1;
    int tot, lst, len[N], lnk[N], nxt[N][S];
    void clear(int x) {
        std::fill(nxt[x], nxt[x] + S, 0);
        len[x] = lnk[x] = 0;
    }
    void clear() {
        clear(tot = lst = 1);
    }
    void insert(int x) {
        int cur = ++tot;
        clear(cur);
        len[cur] = len[lst] + 1;
        int p = lst;
        for (; p && !nxt[p][x]; p = lnk[p]) nxt[p][x] = cur;
        if (!p) {
            lnk[cur] = 1;
        } else {
            int q = nxt[p][x];
            if (len[q] == len[p] + 1) {
                lnk[cur] = q;
            } else {
                int c = ++tot;
                clear(c);
                len[c] = len[p] + 1;
                lnk[c] = lnk[q];
                std::copy(nxt[q], nxt[q] + S, nxt[c]);
                for (; p && nxt[p][x] == q; p = lnk[p]) nxt[p][x] = c;
                lnk[cur] = lnk[q] = c;
            }
        }
        lst = cur;
    }
};

SAM<N, 2> S;

void match(int n) {
    for (int u = 1, l = 0, i = 1; i <= n; i++) {
        int x = s[i] - '0';
        for (; u && !S.nxt[u][x]; l = S.len[u = S.lnk[u]]);
        if (!u) {
            u = 1, l = 0;
        } else {
            u = S.nxt[u][x], l++;
        }
        p[i] = l;
    }
}
bool check(int x, int n) {
    std::fill(f + 1, f + x, 0);
    int l = 1, r = 0;
    for (int i = x; i <= n; i++) {
        for (; l <= r && f[q[r]] - q[r] <= f[i - x] - (i - x); r--);
        q[++r] = i - x;
        for (; l <= r && q[l] < i - p[i]; l++);
        f[i] = f[i - 1];
        if (l <= r) f[i] = std::max(f[i], f[q[l]] + i - q[l]);
    }
    return f[n] * 10 >= n * 9;
}
int main() {
    scanf("%d%d", &n, &m);
    S.clear();
    for (int i = 1; i <= m; i++) {
        scanf("%s", s + 1);
        int len = strlen(s + 1);
        S.lst = 1;
        for (int j = 1; j <= len; j++) S.insert(s[j] - '0');
    }
    for (int i = 1; i <= n; i++) {
        scanf("%s", s + 1);
        int len = strlen(s + 1);
        match(len);
        int l = 0, r = len, ans = 0;
        while (l <= r) {
            int mid = (l + r) >> 1;
            check(mid, len) ? l = (ans = mid) + 1 : r = mid - 1;
        }
        printf("%d\n", ans);
    }
    return 0;
}