题目：https://www.lydsy.com/JudgeOnline/problem.php?id=2806
只想着怎么用后缀数据结构做，其实应该考虑结合其他算法。
可以二分那个长度 L 。设当前二分为 mid ；令 dp[ i ] 表示到 i 位置“熟悉”的最大长度。那么 \( dp[i]=\max(dp[i-1],\max\limits_{j<=i-mid,s[j+1...i] \in S}(dp[j]+(i-j)) ) \) （其中 S 是模式串的所有子串集合）。
关于那个判断，只要先作出以询问串的每个位置 i 为结尾最长能匹配的后缀长度 f[ i ] 就行了。
这个 DP 过程可以用单调队列优化。在 i 位置把 i-mid 的值加入队列。
注意匹配的长度不是自动机对应点的 len ，而是要记一个 ct ，如果顺延的话，ct++ 而不是 ct = len[ go[cr][w] ] 这样。
注意 dp 的时候如果 i < mid ，不仅是不往队列加元素，还不能做转移（比如 s[ 1...i ] 在模式串里出现也不能给 dp[ i ] 赋值）！因为这样匹配上的是长度 <mid 的，不合法。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
int Mx(int a,int b){return a>b?a:b;}
const int N=11e5+;
int n,m,go[N][],len[N],fa[N],cnt=,lst;
int f[N],dp[N],q[N],he,tl; char s[N];
int cz(int p,int w)
{
int q=go[p][w],nq=++cnt; len[nq]=len[p]+;
fa[nq]=fa[q]; fa[q]=nq;
memcpy(go[nq],go[q],sizeof go[q]);
for(;go[p][w]==q;p=fa[p])go[p][w]=nq;
return nq;
}
int ins(int p,int w)
{
if(go[p][w])
{
int q=go[p][w];
if(len[q]==len[p]+)return q;
return cz(p,w);
}
int np=++cnt; len[np]=len[p]+;
for(;p&&!go[p][w];p=fa[p])go[p][w]=np;
if(!p){ fa[np]=;return np;}//fa=1!
int q=go[p][w];
if(len[q]==len[p]+)fa[np]=q; else fa[np]=cz(p,w);
return np;
}
int chk(int mid,int d)
{
he=tl=;
for(int i=;i<=d;i++)
{
dp[i]=dp[i-];
if(i<mid)continue;//not do!!!
int cr=i-mid;
while(he<tl&&dp[q[tl]]-q[tl]<=dp[cr]-cr)tl--;
q[++tl]=cr;
while(he<tl&&q[he+]<i-f[i])he++;
if(he<tl)dp[i]=Mx(dp[i],dp[q[he+]]+i-q[he+]);
}
return dp[d];
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=;i<=m;i++)
{
scanf("%s",s+);
for(int j=,lm=strlen(s+),d=;j<=lm;j++)
d=ins(d,s[j]-'');
}
for(int i=,d;i<=n;i++)
{
scanf("%s",s+);
d=strlen(s+);
for(int j=,cr=,ct=;j<=d;j++)//ct not len[cr]!!
{
int w=s[j]-'';
while(!go[cr][w])cr=fa[cr],ct=len[cr];
if(go[cr][w])cr=go[cr][w],ct++;
else cr=,ct=;
f[j]=ct;
}
int lm=ceil(0.9*d),l=,r=d,ret=;
while(l<=r)
{
int mid=l+r>>;
if(chk(mid,d)>=lm)ret=mid,l=mid+;
else r=mid-;
}
printf("%d\n",ret);
}
return ;
}