首先 发现$L$满足单调性, 可以二分

考虑一个DP​

设$f_i$ 表示将前$i$个元素分成若干段最大有多少被匹配的

转移

$$ f_i = \max(f_j + i - j, f_{i - 1}) \quad (i - len(i) \leq j \leq i - L) $$

$len(i)$ 表示以$i$ 结尾最长能被匹配到的子串的长度, $L$是当前二分的值

如何求出以$i$结尾最长能被匹配的子串长度呢?

一个朴素的方法是对每个位置暴力走, 然后能走多少就是多少, 但复杂度太高

发现走的路程都是重复的, 可以记录一些信息来节省时间.

我们可以从位置1开始暴力匹配, 如果走不下去, 就跳后缀链接再匹配

这样可以充分利用之前的信息, 减少复杂度.

然后观察一下转移方程, 发现状态不能优化, 只能优化转移, 发现一个性质.

$$ i - len(i) \leq i + 1 - len(i + 1) \\i - L < i + 1 - L $$

发现决策的位置是递增的, 于是我们可以维护$f_j - j$ 的单调递减队列.

总体思路就是对$M$个串建广义SAM, 然后对每个询问串, 先预处理$len(i)$

然后二分答案, 用$dp$ check.

总复杂度为$O(\sum{|S|} + \sum{|P|\log|P|})$

代码:

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N = 1e6 + 10;

char s[N];
int tot, fa[N * 2], ch[N * 2][26], len[N * 2], mx[N * 2], f[N * 2];
pair<int, int> qu[N * 2];
inline int insert(int x, int las)
{
    if (ch[las][x] && len[las] + 1 == len[ch[las][x]])
        return ch[las][x];
    int cur = ++tot;
    int p = las;
    int clone = 0;
    int fl = 0;
    len[cur] = len[las] + 1;
    while (p && !ch[p][x])
    {
        ch[p][x] = cur;
        p = fa[p];
    }
    if (p == 0)
        fa[cur] = 1;
    else 
    {
        int q = ch[p][x];
        if (len[p] + 1 == len[q])
            fa[cur] = q;
        else 
        {
            if (p == las) fl = 1;
            clone = ++tot;
            len[clone] = len[p] + 1;
            fa[clone] = fa[q];
            memcpy(ch[clone], ch[q], sizeof(ch[q]));
            while (p && ch[p][x] == q)
            {
                ch[p][x] = clone;
                p = fa[p];
            }
            fa[q] = fa[cur] = clone;
        }
    }
    return fl ? clone : cur;
}

inline bool check(int k, int len)
{
    int res = 0;
    int l = 1, r = 0;
    qu[++r] = make_pair(0, 0);
    for (int i = 0; i < k; i++)
        f[i] = 0;
    for (int i = k; i <= len; i++)
    {
        while (l <= r && qu[l].second < i - mx[i])
            l++;
        if (l > r)
            f[i] = f[i - 1];
        else 
            f[i] = max(f[i - 1], qu[l].first + i);
        int t = i - k + 1;
        while (l <= r && qu[l].first <= f[t] - t)
            r--;
        qu[++r] = make_pair(f[t] - t, t);
        res = max(f[i], res);
    }
    double temp = res;
    double t = (double)(len) * 0.9;
    if (temp >= t)
        return true;
    else 
        return false;
}

signed main()
{
    int n, m;
    cin >> n >> m;
    tot = 1;
    for (int i = 1; i <= m; i++)
    {
        cin >> s + 1;
        int len = strlen(s + 1);
        int las = 1;
        for (int j = 1; j <= len; j++)
            las = insert(s[j] - '0', las);
    }
    for (int i = 1; i <= n; i++)
    {
        cin >> s + 1;
        int leng = strlen(s + 1);
        int cur = 1;
        int res = 0;
        for (int j = 1; j <= leng; j++)
        {
            int x = s[j] - '0';
            while (cur != 1 && !ch[cur][x])
            {
                cur = fa[cur];
                res = len[cur];
            }
            if (!ch[cur][x])
                mx[j] = 0;
            else 
            {
                res += 1;
                mx[j] = res;
                cur = ch[cur][x];
            }
        }
        int l = 0;
        int r = leng;
        while (l < r)
        {
            int mid = (l + r + 1) >> 1;
            if (check(mid, leng))
                l = mid;
            else 
                r = mid - 1;
        }
        cout << l << endl;
    }
    return 0;
}