简要题意
给定 \(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\) 右移，因此决策集合只会往右增长，使用单调队列维护最优决策即可。
代码
#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;
for(int i=1;i<=len;i++);
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=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;
}
}