#P13768. [2019年备战北大冬令营]复读机

    ID: 12976 传统题 1000ms 256MiB 尝试: 1 已通过: 1 难度: 9 上传者: 标签>CF2700KMP数学动态规划单调队列优化字符串最短路数论

[2019年备战北大冬令营]复读机

题目描述

有一个长度为 nn 的字符串 SS。复读机至少复读一次 SS,首次复读前已生成的字符串 UU 为空。每次复读时,可以选择字符串 bb,使得 bb 既是当前 UU 的后缀,又是 SS 的前缀。把 SS 去掉这个前缀后剩下的部分接到 UU 末尾。允许选择空的 bb,此时把完整的 SS 接到末尾。

生成的最终字符串长度不能超过 ww。求复读结束时可能得到的不同长度的个数。

输入格式

第一行一个正整数 TT,表示数据组数。每组第一行两个正整数 n,wn,w,第二行一个长度为 nn 的字符串 SS。

输出格式

输出 TT 行,每行一个整数,表示相应数据可能得到的长度个数。

样例

5
3 10
aab
6 10
bbbaaa
6 10
aaaaab
3 10
bba
3 10
baa
3
1
1
3
3

数据范围

所有测试点满足 T=5T=5。

测试点 nn 上界 ww 上界 附加限制
1 10 只有 a、b
2 20
3–4 100 101810^{18}
5–6 10310^3
7–10 5×1045\times10^4 10510^5
11–12 7×1047\times10^4 101810^{18}
13–16 10510^5
17–20 5×1055\times10^5

原 PDF 题面