Logo Universal Online Judge

UOJ

时间限制:1 s 空间限制:512 MB
Statistics

【题目背景】
小 a 在出题。
【题目描述】
小 a 有两个 idea 序列,每个 idea 都是一个字符串,一个题可以看成一个 idea 子序 列 .按 .顺 .序 .拼 .接的结果。小 a 对两个 idea 序列分别生成了所有的题目。你是小 a 的工具人, 他现在让你验生成的每一道题。
显然,你的工作量巨大,所以你想到了一种剪枝(智将):如果一个题在两边都出现 了,那么可以只验一次。
于是自然地,你不禁发问「 .两 .边 .都 .在 .的 .题 .中 .最 .长 .的 .是 .哪 .道」,你现在想解决这个问题。
由于 idea 个数非常多,我们采取一种特殊的输入方式,见【输入格式】。 .请 .一 .定 .仔 .细 .阅 .读, .这 .可 .能 .对 .你 .很 .重 .要。
【输入格式】
从文件 problem.in 中读入数据。
第一行,两个正整数 n, m,第二行一个长为 n 的字符串 s。
其意义为:
• 第一个 idea 序列为 s 的后缀排序后的前 m 个后缀
• 第二个 idea 序列为 s 的前 m 个后缀
【输出格式】
输出到文件 problem.out 中。
对每组询问输出一行一个整数,代表最长的题的长度。
如果不存在一道题在两边都出现,则输出 0。
【样例 1 输入】

3 2
asd
【样例 1 输出】

3
【样例 1 解释】
第一个序列为 asd, d,第二个序列为 asd, sd。
第一个序列生成的题目为 {asd, d, asdd},第二个序列生成的题目为 {asd, sd, asdsd}。
其最长的公共元素显然是 asd,长度为 3。
【样例 2 输入】

8 3
xgfyayub
【样例 2 输出】

6

【样例 3】 见选手目录下的 problem/problem3.in 与 problem/problem3.ans。
该样例约束与子任务 3 一致。
【测试点约束】
对于所有测试数据:1 ≤ m ≤ n ≤ 5000, m ≤ 100。
本题评测开启捆绑测试。
16.png