← 返回题目列表

Codeforces · 1968/G1

G1. 除法+LCP(简易版)

中文机器翻译题面 查看原题

这是问题的简单版本。在此版本中$$$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$$$。它们的最长公共前缀是一。