第3 1 届全国信息学奥林匹克竞赛 CCF NOI 2014 第二试 竞赛时间：2014 年7 月29 日8:00-13:00 题目名称 动物园 随机数生成器 购票 目录 zoo random ticket 可执行文件名 zoo random ticket 输入文件名 zoo.in random.in ticket.in 输出文件名 zoo.out random.out ticket.out 每个测试点时限 1 秒 5 秒 3 秒 内存限制 512MB 256MB 512MB 测试点数目 10 10 10 每个测试点分值 10 10 10 是否有部分分 否 否 否 题目类型 传统型 传统型 传统型 是否有附加文件 是 是 是 提交源程序须加后缀 对于 Pascal 语言 zoo.pas random.pas ticket.pas 对于 C 语言 zoo.c random.c ticket.c 对于 C++ 语言 zoo.cpp random.cpp ticket.cpp 注意：最终测试时，所有编译命令均不打开任何优化开关。 第 31 届 全 国 信 息 学 奥 林 匹 克 竞 赛 第 二 试 动 物 园 第 2 页 共 9 页 动物园 【问题描述】 近 日 ， 园 长 发 现 动 物 园 中 好 吃 懒 做 的 动 物 越 来 越 多 了 。 例 如 企 鹅 ， 只 会 卖 萌向 游 客 要 吃 的 。 为 了 整 治 动 物 园 的 不 良 风 气 ， 让 动 物 们 凭 自 己 的 真 才 实 学 向 游 客要 吃 的 ， 园 长 决 定 开 设 算 法 班 ， 让 动 物 们 学 习 算 法 。 某 天 ， 园 长 给 动 物 们 讲 解 KMP 算 法 。 园 长 ：“ 对 于 一 个 字 符 串 S， 它 的 长 度 为 L。 我 们 可 以 在O(L)的 时 间 内 ， 求出 一 个 名 为 nex t 的 数 组 。 有 谁 预 习 了 nex t 数 组 的 含 义 吗 ？ ” 熊 猫 ：“ 对 于 字 符 串S 的 前i 个 字 符 构 成 的 子 串 ， 既 是 它 的 后 缀 又 是 它 的 前缀 的 字 符 串 中 （ 它 本 身 除 外 ）， 最 长 的 长 度 记 作 nex t[i]。” 园 长 ：“ 非常好 ！那你能举个 例 子 吗 ？ ” 熊 猫 ：“ 例 S 为 abcababc， 则nex t[5]=2。 因为 S 的 前 5 个 字 符 为 abcab， ab既 是 它 的 后 缀 又 是 它 的 前 缀 ，并且找不 到一 个 更长 的 字 符 串 满足这个 性质。同理，还可 得出 nex t[1] = nex...
