这是问题的简单版本。在此版本中$$$l=r$$$。
给你一个字符串 $$$s$$$。对于固定的 $$$k$$$,考虑将 $$$s$$$ 精确划分为 $$$k$$$ 连续子串 $$$w_1,\dots,w_k$$$。令 $$$f_k$$$ 为所有分区中可能的最大$$$LCP(w_1,\dots,w_k)$$$。
$$$LCP(w_1,\dots,w_m)$$$ 是字符串 $$$w_1,\dots,w_m$$$ 的最长公共前缀的长度。
例如,如果 $$$s=abababcab$$$ 且 $$$k=4$$$,则可能的划分为 $$$\color{red}{ab}\color{blue}{ab}\color{orange}{abc}\color{green}{ab}$$$。 $$$LCP(\color{red}{ab},\color{blue}{ab},\color{orange}{abc},\color{green}{ab})$$$ 是 $$$2$$$,因为 $$$ab$$$ 是这四个字符串的最长公共前缀。请注意,每个子字符串都由一段连续的字符组成,并且每个字符恰好属于一个子字符串。
你的任务是找到$$$f_l,f_{l+1},\dots,f_r$$$。在此版本中$$$l=r$$$。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。
每个测试用例的第一行包含两个整数 $$$n$$$、$$$l$$$、$$$r$$$ ($$$1 \le l = r \le n \le 2 \cdot 10^5$$$) — 字符串的长度和给定范围。
每个测试用例的第二行包含长度为$$$n$$$的字符串$$$s$$$,所有字符均为小写英文字母。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2\cdot 10^5$$$。
输出
对于每个测试用例,输出 $$$r-l+1$$$ 值:$$$f_l,\dots,f_r$$$。
示例
输入 #1
7 3 3 3 aba 3 3 3 aaa 7 2 2 abacaba 9 4 4 abababcab 10 1 1 codeforces 9 3 3 abafababa 5 3 3 zpozp
输出 #1
0 1 3 2 10 2 0
注意
在第一个样本 $$$n=k$$$ 中,因此 $$$aba$$$ 的唯一划分是 $$$\color{red}a\color{blue}b\color{orange}a$$$。答案是零,因为这些字符串没有共同的前缀。
在第二个示例中,唯一的划分是 $$$\color{red}a\color{blue}a\color{orange}a$$$。它们的最长公共前缀是一。