题目描述

这是该问题的简单版本。在本版本中 $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$。

说明/提示

在第一个样例中，$n=k$，所以 $aba$ 的唯一划分方式是 $\color{red}a\color{blue}b\color{orange}a$。答案为零，因为这些字符串没有公共前缀。

在第二个样例中，唯一的划分方式是 $\color{red}a\color{blue}a\color{orange}a$。它们的最长公共前缀为一。

由 ChatGPT 4.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

0
1
3
2
10
2
0