#P18537. Palworld
Palworld
Palworld
一款名为 Palworld 的新游戏正在风靡全球。游戏目标是构造尽可能长的回文串。这是一款解谜游戏!
游戏开始时,你有一个由 个小写英文字母组成的字符串 ,以及整数 。你必须恰好执行一次以下操作:
- 选择位置 ,,在 的第 个字符之后插入至多 个字符。 表示在整个 的最前面插入; 表示在最后面插入。
插入的字符形成一个连续块,插入位置只有一个。允许插入零个字符。
游戏分数等于操作后字符串中最长回文子串的长度。请计算可能取得的最高分数。
回文串是正着读、倒着读都相同的字符串。子串通过删除原串前面和/或后面的若干字符得到,允许不删除;必须连续。
输入格式
第一行一个整数 ,表示测试用例数。每个测试用例占两行:
- 第一行两个整数 ,分别为 的长度和允许插入的最大字符数;
- 第二行字符串 。
限制:
- ;
- ;
- ;
- 只含
a到z; - 同一个输入文件中全部测试用例的 之和不超过 。
输出格式
每个测试用例输出一行,一个整数,表示操作后最长回文子串长度的最大可能值。
原样例
4
1 3
a
4 1
icpc
4 2
icpc
8 4
icecream
4
5
5
11
样例说明
- 第一例可插入 个字符得到
abba,它是长度 的回文串。 - 第二例最优做法是在末尾添加
i,得到长度 的回文串icpci。 - 第三例即使允许插入 个字符,也无法获得更长的回文子串。
- 第四例的一种最优结果是
imaercecream,其中子串maercecream是长度 的回文串。