2636. [CTSC 2012]熟悉的文章

【题目描述】

阿米巴是小强的好朋友。

在小强眼中，阿米巴是一个作文成绩很高的文艺青年。为了获取考试作文的真谛，小强向阿米巴求教。阿米巴给小强展示了几篇作文，小强觉得这些文章怎么看怎么觉得熟悉，仿佛是某些范文拼拼凑凑而成的。小强不禁向阿米巴投去了疑惑的眼光，却发现阿米巴露出了一个狡黠的微笑。

为了有说服力地向阿米巴展示阿米巴的作文是多么让人觉得“眼熟”，小强想出了一个评定作文 “熟悉程度”的量化指标：$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$值比其他同学的明显要大。请你帮他验证一下。

【输入格式】

输入第一行是两个整数 $N, M$，表示待检查的作文数量，和小强的标准作文库的行数。

接下来是$M$行的$01$串，表示标准作文库。

接下来是$N$行的$01$串，表示$N$篇作文。

【输出格式】

输出$N$行，每一行包含一个整数，表示该篇作文的$L_0$值。

【样例输入】

1 2
10110
000001110
1011001100

【样例输出】

4

【提示】

对于$30$%的测试数据，输入文件的长度不超过$1000$字节。

对于$50$%的测试数据，输入文件的长度不超过$61000$字节。

对于$80$%的测试数据，输入文件的长度不超过$250000$字节。

对于$100$%的测试数据，输入文件的长度不超过$1100000$字节。

【来源】

$http://www.tsinsen.com/A1346$