解题思路

设

k=\left\lfloor \frac{x}{2}\right\rfloor

对于某个长度为 $x$ 的子串 $t$ ，构造出的新字符串由三部分拼接而成：

P4636.第1题-不是字符串问题

1000ms

Difficulty: 3

所属公司 : 字节

算法与标签>暴力枚举

对于长度为 $m$ 的字符串 $t_1t_2...t_m$ 和整数 $i(≤i≤m)$ ，我们将字符串 $f_i(t)$ 定义为以下内容的连接：

现在，对于长度为 $n$ 的字符串 $s_1s_2...s_n$ ，你需要取出它的的全部长度为 $x$ 的子串，且令 $i=x$ ，按照上方所述的步骤进行构造，能构造出多少个不相同的新字符串？

定义子串为，从原字符串中，连续的选择一段字符(可以全选、可以不选)组成的新字符串。

每个测试文件均包含多组测试数据。第一行输入一个整数 $T(1≤T≤100)$ 代表数据组数，每组测试数据描述如下：

第一行上输入两个整数 $n,x(1≤n≤100;1≤x≤n)$ 代表字符串长度、和询问长度。

第二行输入一个长度为 $n$ ，且由大小写字母混合构成的字符串 $s$ ，代表初始串。

在一行上输出一个整数，代表构造出的新字符串数量。

输入

2
5 4
bAbbb
7 3
nuhhhhh

输出

1
3

说明

对于第一组测试数据，长度为 $4$ 的不同子串有 $bAbb$ 和 $Abbb$ :

对于 $bAbb$ ，构造得到 $f4 (bAbb)= Ab +bbbA +bb$ ：
- 前 $\frac{i}{2}$ 个字符，按字典序从小到大排序为 $Ab$
- 整串，按字典序从大到小排序为 $bbbA$ ;
- 除去前 $\frac{i}{2}$ 个字符外的剩余字符，按字典序从小到大排序为 $bb$ 。
对于 $Abbb$ ，构造得到 $f4 (Abbb)= Ab +bbbA +bb$ 。

编辑器加载中…

输入

预期输出（选填）