题目
题目描述
阿米巴是小强的好朋友。
在小强眼中，阿米巴是一个作文成绩很高的文艺青年。为了获取考试作文的真谛，小强向阿米巴求教。阿米巴给小强展示了几篇作文，小强觉得这些文章怎么看怎么觉得熟悉，仿佛是某些范文拼拼凑凑而成的。小强不禁向阿米巴投去了疑惑的眼光，却发现阿米巴露出了一个狡黠的微笑。
为了有说服力地向阿米巴展示阿米巴的作文是多么让人觉得“眼熟”，小强想出了一个评定作文 “熟悉程度”的量化指标：L 0 .小强首先将作文转化成一个 01 串。之后，小强搜集了各路名家的文章，同样分别转化成 01 串后，整理出一个包含了 M 个 01 串的“ 标准作文库 ”。
小强认为：如果一个 01 串长度不少于 L 且在 标准作文库 中的某个串里出现过（即，它是 标准作文库 的 某个串 的一个 连续子串 ），那么它是“ 熟悉 ”的。对于一篇作文（一个 01 串）A，如果能够把 A 分割成若干段子串，其中“ 熟悉 ” 的子串的 长度 总 和 不少于 A 总 长度的 90%，那么称 A 是 “ 熟悉的文章 ”。 L 0 是 能够让 A 成为 “ 熟悉的文章 ” 的 所有 L 的最大值 （如果不存在这样的 L，那么规定 L 0 =0）。
举个例子：
小强的作文库里包含了如下 2 个字符串：
10110
000001110
有一篇待考察的作文是：
1011001100
小强计算出这篇作文 L 的最大值是 4，因为待考察的作文可以视作’10110’+’0110’+’0’，其中’10110’和’0110’被判定为 “ 熟悉 ” 的。而当 L = 5 或是更大的时候，不存在符合题意的分割方法。所以，这篇作文的 L 0 = 4。小强认为阿米巴作文的 L 0 值比其他同学的明显要大。请你帮他验证一下。
输入输出格式
输入格式：
输入文件 cheat.in 第一行是两个整数 N, M，表示待检查的作文数量，和小强的标准作文库的行数。
接下来是 M 行的 01 串，表示标准作文库。
接下来是 N 行的 01 串，表示 N 篇作文。
输出格式：
输出文件 cheat.out 包含 N 行，每一行包含一个整数，表示该篇作文的 L 0 值。
输入输出样例
输入样例#1：
1 2
10110
000001110
1011001100
输出样例#1：
4
说明
对于 30%的测试数据，输入文件的长度不超过 1000 字节。
对于 50%的测试数据，输入文件的长度不超过 61000 字节。
对于 80%的测试数据，输入文件的长度不超过 250000 字节。
对于 100%的测试数据，输入文件的长度不超过 1100000 字节。
题解
假设已经知道每个点往前能最长匹配多少字符$Lmax$（这个可以用$SAM$搞出来），现在有一个$L$，要判断这个$L$是否合法，不难想到用$f_i$表示前$i$位匹配的最长长度
则有：$f_i=max(f_{j-1}+i-j+1),j\ge i-Lmax_i+1,j\ge i-L+1$
发现如果只有$j\ge i-L+1$，这个就可以用单调队列优化了
可以发现$i-Lmax_i+1$是单调不减的，假设对于某个$i$有$j$，使得$j>i,Lmax_j-j+1< Lmax_i-i+1$，对于$Lmax_j-j+1$到$Lmax_i-i+1$这部分，从$i$匹配肯定也可以匹配上，得证
所以还是可以用单调队列优化了
对于每个$L$，发现某个大的$L$成立，小于ta的$L$肯定也可以成立，所以可以二分$L$了
代码
# include<iostream>
# include<cstring>
# include<cstdio>
# include<algorithm>
using namespace std;
const int MAX=2.2e6+5;
int N,M,n;
char a[MAX];
struct SAM{
int l,r,L;
int len[MAX],fa[MAX],L_max[MAX],qu[MAX],f[MAX];
int son[MAX][2];
SAM() {l=r=1;}
void ins(int x)
{
int tt=r;
len[r=++l]=++L;
for(;tt&&!son[tt][x];tt=fa[tt])
son[tt][x]=r;
if(!tt) return void(fa[r]=1);
int qwq=son[tt][x];
if(len[qwq]==len[tt]+1) return void(fa[r]=qwq);
len[++l]=len[tt]+1,fa[l]=fa[qwq],fa[qwq]=fa[r]=l,son[l][0]=son[qwq][0],son[l][1]=son[qwq][1];
for(int i=tt;son[i][x]==qwq;i=fa[i])
son[i][x]=l;
}
void Init(int _n)
{
for(int i=1,x=1,_L=0;i<=_n;++i)
{
if(son[x][a[i]-'0']) x=son[x][a[i]-'0'],++_L;
else
{
while(x&&!son[x][a[i]-'0']) x=fa[x];
if(!x) x=1,_L=0;
else _L=len[x]+1,x=son[x][a[i]-'0'];
}
L_max[i]=_L;
}
}
bool look(int mid,int _n)
{
for(int i=1;i<mid;++i)
f[i]=0,qu[i]=0;
for(int i=mid,hl=1,tl=1;i<=_n;++i)
{
f[i]=f[i-1];
while(hl<=tl&&qu[hl]<i-L_max[i]) ++hl;
if(hl<=tl) f[i]=max(f[i],f[qu[hl]]+i-qu[hl]);
while(hl<=tl&&f[qu[tl]]-qu[tl]<=f[i-mid+1]-i+mid-1) --tl;
qu[++tl]=i-mid+1;
}
return f[_n]*10>=_n*9;
}
int Solve(int _n)
{
int l=1,r=_n,ans=0;
Init(_n);
while(l<=r)
{
int mid(l+r>>1);
if(look(mid,_n)) ans=mid,l=mid+1;
else r=mid-1;
}
return ans;
}
}_S;
int main()
{
scanf("%d%d",&N,&M);
for(int i=1,_n;i<=M;++i,_S.r=1,_S.L=0)
{
scanf("%s",a+1),_n=strlen(a+1);
for(int j=1;j<=_n;++j)
_S.ins(a[j]-'0');
}
for(int i=1,_n;i<=N;++i)
scanf("%s",a+1),_n=strlen(a+1),printf("%d\n",_S.Solve(_n));
return 0;
}
