#P4022. [CTSC2012] 熟悉的文章

    ID: 1018 远端评测题 1000ms 250MiB 尝试: 1 已通过: 1 难度: 10 上传者: 标签>字符串2012WC/CTSC/集训队后缀自动机SAM

[CTSC2012] 熟悉的文章

题目描述

阿米巴是小强的好朋友。

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

为了有说服力地向阿米巴展示阿米巴的作文是多么让人觉得“眼熟”,小强想出了一个评定作文 “熟悉程度”的量化指标:L0L_0 .小强首先将作文转化成一个 0101 串。之后,小强搜集了各路名家的文章,同样分别转化成 0101 串后,整理出一个包含了 MM0101 串的 “ 标准作文库 ”。

小强认为:如果一个 0101 串长度不少于 LL 且在标准作文库中的某个串里出现过(即,它是标准作文库的某个串的一个 连续子串),那么它是 “ 熟悉 ” 的。对于一篇作文(一个 0101 串)AA,如果能够把 AA 分割成若干段子串,其中 “ 熟悉 ” 的子串的长度总和不少于 AA 总长度的 90%90\%,那么称 AA 是 “ 熟悉的文章 ”。 L0L_0 是能够让 AA 成为 “ 熟悉的文章 ” 的 所有 LL 的最大值 (如果不存在这样的 LL,那么规定 L0=0L_0=0)。

举个例子:

小强的作文库里包含了如下 22 个字符串:

10110
000001110

有一篇待考察的作文是:

1011001100

小强计算出这篇作文 LL 的最大值是 44,因为待考察的作文可以视作 10110+0110+010110+0110+0,其中 101101011001100110 被判定为 “熟悉” 的。而当 L=5L = 5 或是更大的时候,不存在符合题意的分割方法。所以,这篇作文的 L0=4L_0 = 4。小强认为阿米巴作文的 L0L_0 值比其他同学的明显要大。请你帮他验证一下。

输入格式

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

接下来是 MM 行的 0101 串,表示标准作文库。

接下来是 NN 行的 0101 串,表示 NN 篇作文。

输出格式

输出包含 NN 行,每一行包含一个整数,表示该篇作文的 L0L_0 值。

1 2
10110
000001110
1011001100
4

提示

对于 30%30\% 的测试数据,输入文件的长度不超过 10001000 字节。

对于 50%50\% 的测试数据,输入文件的长度不超过 6100061000 字节。

对于 80%80\% 的测试数据,输入文件的长度不超过 250000250000 字节。

对于 100%100\% 的测试数据,输入文件的长度不超过 11000001100000 字节。