#P8795. [2017年江苏]神奇的重复序列

[2017年江苏]神奇的重复序列

Problem 3. 神奇的重复序列

2s / 1024mb

题目描述

幽香今天在思考一个关于字符串的问题。

幽香面前有一个长度为nn的字符串ss,幽香可以选择串ss 的最多kk个位置,并将这些位置上的字符替换成任何她想要的字符。

幽香想要使得修改之后,新的串中出现至少两次的连续子串的长度尽量长 (这两次出现可以有重合)。

你能帮帮她吗?

输入格式

第一行一个非负整数 kk,表示最多的修改位置数量。修改位置超过串长没有额外作用;当 k≥n−1k\ge n-1 时,总能把整串改成同一字符,答案为 n−1n-1。

接下来一整行表示字符串 ss,按这一行的字符读取,不要求字符必须是小写字母;行内空格也作为字符串的字符。

输出格式

输出修改之后的出现至少两次的连续子串的最长长度。

样例输入

2
tmirkoxlyzmirkoslav

样例输出

8

数据范围和约定

20%的数据满足 1≤∣S∣≤201\le\lvert S\rvert\le20;50%满足 1≤∣S∣≤3001\le\lvert S\rvert\le300;全部数据满足 1≤∣S∣≤30001\le\lvert S\rvert\le3000。