P4022 [CTSC2012]熟悉的文章

    • 307通过
    • 720提交
  • 题目提供者 rill7747
  • 评测方式 云端评测
  • 标签 后缀自动机,SAM 字符串 WC/CTSC/集训队 2012
  • 难度 NOI/NOI+/CTSC
  • 时空限制 1000ms / 256MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

    阿米巴是小强的好朋友。

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

    为了有说服力地向阿米巴展示阿米巴的作文是多么让人觉得“眼熟”,小强想出了一个评定作文 “熟悉程度”的量化指标: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 字节。

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。