1001. 串串

题目描述

• 定义一个字符串 t 为 k 优秀的，当且仅当满足以下条件：

• t = A1 + A2 + ⋯ + Ak，其中 “+” 表示字符串连接；

• 对于所有 i ≥ 2，有 ∣Ai ∣ = ∣Ai−1 ∣ + 1。对于一个字符串 t，我们

用 ∣t∣ 表示串 t 的长度；

• ∣A1 ∣ ≥ 1；

• 对于所有 i ≥ 2，有 lcp（Ai, Ai−1）= ∣Ai−1 ∣。

其中 lcp（x, y） 表示字符串 x 与 y 的 最长公共前缀长度。也就是说， lcp（x, y） 表示从开头开始，x 和 y 有多少个连续的字符是相同的。例如：

• lcp（"abcde", "abf"） = 2；

• lcp（"aaaa", "aa"） = 2；

• lcp（"abc", "xyz"） = 0。

给定一个长度为 n 的、仅由小写字母组成的字符串 s 和一个正整数 k，请你计算字符串中有多少个子串是 k 优秀的。两个子串 s[L1, R1 ] 和 s[L2, R2 ] 被认为不同，当且仅当满足以下任意

一个条件：

• L1 = L2；

• R1 = R2。

输入格式

每个测试文件包含多组测试数据。

第一行包含一个整数 T = 1505，表示测试数据的组数。对于每组测试数据：

• 第一行包含两个整数 n（1 ≤ n ≤ 105）和 k （2 ≤ k ≤ 2 × 105），具体含义见题面；

• 第二行包含一个长度为 n 的字符串 s。

数据保证 ∑ n ≤ 5 × 105。

输出格式

对于每组测试数据，输出一个整数，表示满足条件的 k 优秀子串的数量。

样例输入

2
5 2
aaaaa
7 3
aababca

样例输出

4
1

提示

对于第二组样例，唯一优秀的字符串为 s[1, 6]，可以表示为 "a" +"ab" + "abc"。

来源：官方题面 PDF（2026"钉耙编程"暑期联赛 第10场）