题目概述

Luogu4022

解题报告

不难想到二分答案 $mid$ ，然后求 $L\ge mid$ 是否可行。

令 $K={\lfloor{len\over 10}\rfloor}$ ，那么舍弃的位置不能超过 $K$ 。考虑DP：

$$ f_i=\min\{f_{i-1}+1,\min\{f_{j-1}|i-j+1\ge mid\land S[j,i]\in T\}\} $$

其中 $T$ 是模板串的子串集合，考虑把DP转移条件量化一下，将模板串建出广义SAM，则我们可以得出 $S$ 的每个位置往后的最大匹配长度 $cnt_i$ 。

$$ f_i=\min\{f_{j-1}|i-j+1\ge mid\land j+cnt_j-1\ge i\} $$

不难发现这个DP是可以用线段树来维护的，但是我们观察下性质可以得出一个更优秀的做法。

对于 $j<k<i$ ，如果 $j+cnt_j-1\ge i$ ，那么一定有 $k+cnt_k-1\ge i$（根据子串性质显然可以得出）。因此，如果 $j<k,f_{j-1}\ge f_{k-1}$ ，那么 $j$ 一定是没有用的。有了这个条件，我们就可以用单调队列来维护DP。

示例程序

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=1100000,maxt=maxn<<1,maxi=2;

int n,m;char s[maxn+5];
int pl,ro,son[maxt+5][maxi],fai[maxt+5],MAX[maxt+5];
int K,len,cnt[maxn+5],f[maxn+5],que[maxn+5];

inline int newnode() {pl++;return pl;}
int Extend(int p,int c){
    if (son[p][c]){
        int q=son[p][c];if (MAX[p]+1==MAX[q]) return q;
        int nq=newnode();MAX[nq]=MAX[p]+1;for (int i=0;i<maxi;i++) son[nq][i]=son[q][i];
        fai[nq]=fai[q];fai[q]=nq;while (p && son[p][c]==q) son[p][c]=nq,p=fai[p];
        return nq;
    } else {
        int np=newnode();MAX[np]=MAX[p]+1;
        while (p && !son[p][c]) son[p][c]=np,p=fai[p];
        if (!p) {fai[np]=ro;return np;}
        int q=son[p][c];if (MAX[p]+1==MAX[q]) {fai[np]=q;return np;}
        int nq=newnode();MAX[nq]=MAX[p]+1;for (int i=0;i<maxi;i++) son[nq][i]=son[q][i];
        fai[nq]=fai[q];fai[q]=fai[np]=nq;while (p && son[p][c]==q) son[p][c]=nq,p=fai[p];
        return np;
    }
}
bool check(int mid){
    int Head=1,Tail=0;
    for (int i=1;i<=len;i++){
        f[i]=f[i-1]+1;
        if (i>=mid){
            while (Head<=Tail && f[que[Tail]-1]>=f[i-mid]) Tail--;
            que[++Tail]=i-mid+1;
        }
        while (Head<=Tail && que[Head]+cnt[que[Head]]-1<i) Head++;
        if (Head<=Tail) f[i]=min(f[i],f[que[Head]-1]);
    }
    return f[len]<=K;
}
int main(){
    scanf("%d%d",&n,&m);
    ro=newnode();
    for (int t=1;t<=m;t++){
        scanf("%s",s+1);len=strlen(s+1);
        for (int i=len,p=ro;i;i--) p=Extend(p,s[i]-'0');
    }
    for (int t=1;t<=n;t++){
        scanf("%s",s+1);len=strlen(s+1);K=len/10;
        for (int i=len,p=ro,now=0;i;i--){
            while (p && !son[p][s[i]-'0']) p=fai[p],now=MAX[p];
            if (p) p=son[p][s[i]-'0'],now++; else p=ro,now=0;
            cnt[i]=now;
        }
        int L=1,R=len;
        for (int mid=L+(R-L>>1);L<=R;mid=L+(R-L>>1))
            check(mid)?L=mid+1:R=mid-1;
        printf("%d\n",R);
    }
    return 0;
}