#PQJ85x10789. QOJ 85_10789
QOJ 85_10789
IOI2012 中国队选拔赛暨精英赛 第二试 熟悉的文章 熟悉的文章 【问题描述】 阿米巴是小强的好朋友。 在小强眼中,阿米巴是一个作文成绩很高的文艺青年。为了获取考试作文的 真谛,小强向阿米巴求教。阿米巴给小强展示了几篇作文,小强觉得这些文章怎 么看怎么觉得熟悉,仿佛是某些范文拼拼凑凑而成的。小强不禁向阿米巴投去了 疑惑的眼光,却发现阿米巴露出了一个狡黠的微笑。 为了有说服力地向阿米巴展示阿米巴的作文是多么让人觉得“眼熟”,小强想 出了一个评定作文 “熟悉程度”的量化指标:L0. 小强首先将作文转化成一个01 串。 之后,小强搜集了各路名家的文章,同样分别转化成01 串后,整理出一个 包含了M 个01 串的“标准作文库”。 小强认为:如果一个01 串长度不少于L 且在标准作文库中的某个串里出现 过(即,它是标准作文库的某个串的一个连续子串),那么它是“熟悉”的。对于 一篇作文(一个01 串)A,如果能够把A 分割成若干段子串,其中“熟悉”的子 串的长度总和不少于A 总长度的90%,那么称A 是“熟悉的文章”。 L0 是能够 让A 成为“熟悉的文章”的所有L 的最大值(如果不存在这样的L,那么规定L0 = 0)。 举个例子: 小强的作文库里包含了如下2 个字符串: 10110 000001110 有一篇待考察的作文是: 1011001100 小强计算出这篇作文L 的最大值是4,因为待考察的作文可以视作 '10110'+'0110'+'0',其中'10110'和'0110'被判定为“熟悉”的。而当L = 5 或是更大 的时候,不存在符合题意的分割方法。所以,这篇作文的L0 = 4。 小强认为阿米巴作文的L0 值比其他同学的明显要大。请你帮他验证一下。 【输入格式】 输入文件cheat.in 第一行是两个整数 N, M,表示待检查的作文数量,和小 强的标准作文库的行数。 接下来是M 行的01 串,表示标准作文库。 接下来是N 行的01 串,表示N 篇作文。 【输出格式】 输出文件cheat.out 包含N 行,每一行包含一个整数,表示该篇作文的L0 值。 第2 页 共5 页 IOI2012 中国队选拔赛暨精英赛 第二试 熟悉的文章 【样例输入】 1 2 10110 000001110 1011001100 【样例输出】 4 【样例说明】 这就是题目描述里的例子。 【数据规模】 对于30%的测试数据,输入文件的长度不超过1000 字节。 对于50%的测试数据,输入文件的长度不超过61000 字节。 对于80%的测试数据,输入文件的长度不超过250000 字节。 对于100%的测试数据,输入文件的长度不超过1100000 字节。 第3 页 共5 页