熟悉的文章（后缀自动机+二分答案+单调队列）

熟悉的文章

题意：

给定一本包含 $M$M个字符串（ $01$01串）的字典，然后给出 $N$N个字符串，要求输出一个最大的长度 $L$L。其中 $L$L满足当前字符串 $90$90%以上的部分都能被字典中的字符串的子串（子串长度不小于 $L$L）表示。

思路：

1. 既然是与子串相关的问题，先考虑建立后缀自动机（在字典中每个字符串中间插入不会出现的字符进行字符串的分割），这样就能进行子串的匹配。
2. 题目要求最大的 $L$L，由于 $L$L越小肯定容易合理，也就是 $L$L是否合理是与 $L$L的大小是呈单调性的，我们自然而然地会想到采用二分答案。
3. 而对于每个字符串，它的每一个位置（ $i$i）都对应了一个以当前位置结尾的最长可识别后缀（长度为 $rl\left[i\right]$rl[i]），这个后缀长度显然可以预处理得到（一种常用技巧）。
4. 具体到如何分配字符串的哪些部分为可识别以最小化不可识别的部分，我们可以采用 $dp$dp；设 $dp\left[i\right]$dp[i]为字符串 $[1,i]$[1,i]中不可识别的字符的最小数量，则转移方程为： $dp\left[i\right]=min\left(dp\right[i-1],dp[j\left]\right)$dp[i]=min(dp[i−1],dp[j])，其中 $j$j满足 $[j+1,i]$[j+1,i]为一个可识别的子串（长度大于等于 $L$L），而怎样得到最优的 $j$j使得 $dp\left[i\right]$dp[i]最小呢？
5. 有一个很明显的观察： $i-rl\left[i\right]$i−rl[i]是单调不减的（其实也不明显，但很容易验证）。同时，对于两个位置 $a,b$a,b，若 a<b且 $dp\left[a\right]>dp\left[b\right]$dp[a]>dp[b]，则 $dp\left[a\right]$dp[a]显然在任何时候都不会成为最优的 $j$j。以上的描述表明我们可以维护一个单调递增的队列！
6. 这样，我们就可以在 $O\left(nlogn\right)$O(nlogn)的时间复杂度内处理单个字符串询问。

题面描述

#include "bits/stdc++.h"
#define hhh printf("hhh\n")
#define see(x) (cerr<<(#x)<<'='<<(x)<<endl)
using namespace std;
typedef long long ll;
typedef pair<int,int> pr;
inline int read() {int x=0;char c=getchar();while(c<'0'||c>'9')c=getchar();while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();return x;}

const int maxn = 6e6+10;
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
const double eps = 1e-7;

int N, M, ml;
char s[maxn];
int ch[maxn][3], fa[maxn], len[maxn];
int last=1, tot=1;
int dp[maxn], que[maxn], rl[maxn];

void add(int c) {
    int p=last, np=last=++tot;
    len[np]=len[p]+1;
    for(; p&&!ch[p][c]; p=fa[p]) ch[p][c]=np;
    if(!p) fa[np]=1;
    else {
        int q=ch[p][c];
        if(len[q]==len[p]+1) fa[np]=q;
        else {
            int nq=++tot; len[nq]=len[p]+1;
            fa[nq]=fa[q], fa[np]=fa[q]=nq;
            memcpy(ch[nq],ch[q],12);
            for(; p&&ch[p][c]==q; p=fa[p]) ch[p][c]=nq;
        }
    }
}

void pre() {
    int curlen=0, now=1, l=strlen(s+1);
    for(int i=1; i<=l; ++i) {
        int c=s[i]-'0';
        if(ch[now][c]) curlen++, now=ch[now][c];
        else {
            for(; now&&!ch[now][c]; now=fa[now]);
            if(now) curlen=len[now]+1, now=ch[now][c];
            else curlen=0, now=1;
        }
        rl[i]=curlen;
    }
}

bool check(int L) {
    int l=strlen(s+1), head=1, tail=0;
    for(int i=1; i<=l; ++i) {
        dp[i]=dp[i-1]+1;
        if(i>=L) {
            while(head<=tail&&dp[que[tail]]>=dp[i-L]) tail--;
            que[++tail]=i-L;
        }
        while(head<=tail&&que[head]<i-rl[i]) head++;
        if(head<=tail) dp[i]=min(dp[i],dp[que[head]]);
    }
    if(dp[l]<=l/10) return 1;
    return 0;
}

int main() {
    //ios::sync_with_stdio(false); cin.tie(0);
    scanf("%d%d", &N, &M);
    for(int i=1; i<=M; ++i) {
        scanf("%s", s);
        int l=strlen(s);
        if(l>ml) ml=l;
        for(int i=0; i<l; ++i) add(s[i]-'0');
        add(2);
    }
    while(N--) {
        scanf("%s", s+1); pre();
        int l=1, r=ml+1, m=(l+r)/2;
        while(l<r) {
            if(check(m)) l=m+1;
            else r=m;
            m=(l+r)/2;
        }
        cout<<m-1<<endl;
    }
}