#P13768. [2019年备战北大冬令营]复读机
[2019年备战北大冬令营]复读机
题目描述
有一个长度为 的字符串 。复读机至少复读一次 ,首次复读前已生成的字符串 为空。每次复读时,可以选择字符串 ,使得 既是当前 的后缀,又是 的前缀。把 去掉这个前缀后剩下的部分接到 末尾。允许选择空的 ,此时把完整的 接到末尾。
生成的最终字符串长度不能超过 。求复读结束时可能得到的不同长度的个数。
输入格式
第一行一个正整数 ,表示数据组数。每组第一行两个正整数 ,第二行一个长度为 的字符串 。
输出格式
输出 行,每行一个整数,表示相应数据可能得到的长度个数。
样例
5
3 10
aab
6 10
bbbaaa
6 10
aaaaab
3 10
bba
3 10
baa
3
1
1
3
3
数据范围
所有测试点满足 。
| 测试点 | 上界 | 上界 | 附加限制 |
|---|---|---|---|
| 1 | 10 | 只有 a、b |
|
| 2 | 20 | ||
| 3–4 | 100 | ||
| 5–6 | |||
| 7–10 | |||
| 11–12 | |||
| 13–16 | |||
| 17–20 | |||