妈妈我能独立切CTSC黑题啦！
（虽然我承认这题不算难）
以下，用$S(l,r)$表示字符串$S$从$l$位置开始到$r$的子串，$n$表示待考察作文串的长度。
答案很明显有单调性。因为若长度$i$可行的话，则存在和长度$i$相同的方案使所有$j(<i)$也可行。
考虑二分答案。设$rr[i]$表示最大的满足$S(i,rr[i])$为作文库子串的位置。
把所有作文库的串用特殊字符隔开造$SAM$，枚举每个位置匹配预处理$rr[i]$。
容易发现$rr[i]$的一个性质：$rr[i]\ge rr[i-1]$。这样处理$rr[i]$时就可以用上$rr[i-1]$和它结束的节点继续匹配。
这里就有一个问题：以匹配$S(i-1,rr[i-1])$和$S(i,rr[i-1])$到达的节点可能不同，但若不同则一定是$parent\ tree$上的父子关系。记$node$为$i-1$匹配结束的节点，处理第$i$位时，就需要判断一下$S(i,rr[i-1])$的长度和$len[fa[node]]$的关系，选择是否向上跳。$rr[i]$就能$O(n)$预处理了。
对于当前答案$mid$是否可行，可以用$DP$求解。设$f(i)$表示对串$S(i,n)$进行分段，最少有多少个字符是“不熟悉”的。
方程：$f(i)=\min\{f(i+1)+1,f(j)\}(i+mid\le j\le rr[i]+1)$
也就是把第$i$个字符归为“不熟悉”的子串里，或者以第$i$个字符开头划分一段子串。$f(j)$可以用单调队列优化，复杂度为$O(n)$，总复杂度$O(n\log n)$
若$f(1)\le \frac{n}{10}$则答案可行。
代码：
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#define maxn 1100005
#define inf 0x3f3f3f3f
using namespace std;
inline int read(){
int x=0,y=0;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')y=1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
return y?-x:x;
}
#define son(x,y) son[x][y]
int son[maxn][3],fa[maxn],len[maxn],rr[maxn],f[maxn],last=1,cnt=1,n;
char s[maxn];
struct MonoQueue{
int line[maxn],head,tail;
inline void push(int x){
while(head<=tail&&f[line[tail]]>=f[x])--tail;
line[++tail]=x;
}
inline void check(int x){
while(head<=tail&&line[head]>x)++head;
}
inline void clear(){
head=1,tail=0;
}
inline int front(){
if(head<=tail)return f[line[head]];
return inf;
}
}q;//手写单调队列
void insert(int c){
int p=last,ne=last=++cnt;
while(p&&!son(p,c))son(p,c)=ne,p=fa[p];
if(!p)fa[ne]=1;
else {
int q=son(p,c);
if(len[q]==len[p]+1)fa[ne]=q;
else {
int sp=++cnt;
son(sp,0)=son(q,0),son(sp,1)=son(q,1),son(sp,2)=son(q,2);
fa[sp]=fa[q],len[sp]=len[p]+1;
fa[q]=fa[ne]=sp;
while(p&&son(p,c)==q)son(p,c)=sp,p=fa[p];
}
}
}
void work_rr(){
int node=1,l=0;
for(register int i=1;i<=n;++i){
if(l)--l;
if(node!=1&&len[fa[node]]>=l)node=fa[node];
while(i+l<=n&&son(node,s[i+l]-'0'))node=son(node,s[i+l]-'0'),++l;
rr[i]=i+l-1;
}
}
bool check(int l){
q.clear(),f[n+1]=0;
for(register int i=n;i;--i){
if(i+l<=n+1)q.push(i+l);
q.check(rr[i]+1);
f[i]=min(f[i+1]+1,q.front());
}
return f[1]<=n/10;
}
int main(){
int N=read(),M=read(),l,r,mid;
for(register int i=1;i<=M;++i){
scanf("%s",s+1),n=strlen(s+1);
for(register int j=1;j<=n;++j)insert(s[j]-'0');
if(i!=M)insert(2);//特殊字符
}
while(N--){
scanf("%s",s+1),n=strlen(s+1);
work_rr();
l=0,r=n;
while(l<r){
mid=l+r+1>>1;
if(check(mid))l=mid;
else r=mid-1;
}
printf("%d\n",l);
}
}
