P4022 [CTSC2012]熟悉的文章 题解

· · 题解

更好的阅读体验

简要题意

给定 m 个模板串和 n 个匹配串，如果一个字符串是一个模板串的子串且长度不小于 L 则称其为“熟悉的”，对于每个匹配串，求一个最大的 L，满足将匹配串分割，熟悉的子串的总长度大于原串长度的 90\%。

题目分析

首先对于 L，如果有更大的 L 满足了它也一定满足，因此我们首先对其进行二分。

由于跟子串问题相关，且有多个模板串，我们根据模板串建出广义 SAM，分割这种方式有不可在某一位置重复的特点，因此可以考虑对其进行 DP，从前缀开始考虑，一遍 DP 一遍在 SAM 上匹配，求出当前前缀最长熟悉后缀。

设 f_i 表示割到 i 的最大熟悉长度，len_k 表示 SAM 上当前节点的最大长度，则有

f_i=\max(f_{i-1},f_j+(i-j)),j\in [i-len_k,i-L]

继续观察这个转移方程，由于我们是在 SAM 匹配，失败时往父节点走，i-len_k 递增，成功时不变，而 i-L 随 i 右移，因此决策集合只会往右增长，使用单调队列维护最优决策即可。

代码

// Problem: P4022 [CTSC2012]熟悉的文章
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P4022
// Memory Limit: 250 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector> 
#include<queue>
#include<deque>
#define ll long long
using namespace std;
int tot=1,nex[3000001][2],le[3000001],fa[3000001];
int dp[3000001];
string s;
struct Node{
    int last,num;
};
queue<Node> q;
deque<Node> p;
void inserttrie(string s){
    int p=1,len=s.length();
    for(int i=0;i<len;i++){
        int num=s[i]-'0';
        if(!nex[p][num]) nex[p][num]=++tot;
        p=nex[p][num];
    }
}
int insertsam(int last,int num){
    int p=last,np=nex[last][num];le[np]=le[p]+1;
    p=fa[p];
    for(;p && !nex[p][num];p=fa[p]) nex[p][num]=np;
    if(!p) fa[np]=1;
    else{
        int q=nex[p][num];
        if(le[q]==le[p]+1) fa[np]=q;
        else{
            int clone=++tot;le[clone]=le[p]+1;
            for(int i=0;i<=1;i++)nex[clone][i]=(le[nex[q][i]]?nex[q][i]:0);
            for(;p && nex[p][num]==q;p=fa[p]) nex[p][num]=clone;
            fa[clone]=fa[q];fa[q]=fa[np]=clone;
        }
    }
    return np;
}
void build(){
    for(int i=0;i<=1;i++) if(nex[1][i]) q.push((Node){1,i});
    while(!q.empty()){
        int last=q.front().last,num=q.front().num;q.pop();
        int cur=insertsam(last,num);
        for(int i=0;i<=1;i++) if(nex[cur][i]) q.push((Node){cur,i});
    }
}
bool solve(string s,int ans){
    int len=s.length(),now=1,lth=0;
    while(p.size()) p.pop_back();
    for(int i=0;i<len;i++){
        dp[i+1]=dp[i];
        int num=s[i]-'0';
        while(p.size() && (i+1-ans>=0 && dp[i+1-ans]-i-1+ans>p.front().last)){
            p.pop_front();
        }
        if(i+1-ans>=0) p.push_front((Node){dp[i+1-ans]-i-1+ans,i+1-ans});
        while(!nex[now][num] && now){
            now=fa[now];
            lth=le[now];
        }
        if(!now){now=1;lth=0;continue;}
        now=nex[now][num];lth++;
        while(p.size() && i+1-lth>p.back().num) p.pop_back();
        if(p.size())dp[i+1]=max(dp[i+1],p.back().last+i+1);
    }
    double num=len*1.0/10*9;
    if(num<=dp[len]) return true;
    else return false;
}
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>s;
        inserttrie(s);
    }
    build();
    for(int i=1;i<=n;i++){
        cin>>s;
        int l=1,r=s.length();
        while(l<r){
            int mid=(l+r+1)>>1;
            if(solve(s,mid)) l=mid;
            else r=mid-1;
        }
        cout<<l<<endl;
    }
}