Division + LCP (easy version)
Contest: Codeforces Round 943 (Div. 3)
Difficulty rating: 1900
Tags: binary search, data structures, dp, hashing, string suffix structures, strings

This is the easy version of the problem. In this version $$$l=r$$$.

You are given a string $$$s$$$. For a fixed $$$k$$$, consider a division of $$$s$$$ into exactly $$$k$$$ continuous substrings $$$w_1,\dots,w_k$$$. Let $$$f_k$$$ be the maximal possible $$$LCP(w_1,\dots,w_k)$$$ among all divisions.

$$$LCP(w_1,\dots,w_m)$$$ is the length of the Longest Common Prefix of the strings $$$w_1,\dots,w_m$$$.

For example, if $$$s=abababcab$$$ and $$$k=4$$$, a possible division is $$$\color{red}{ab}\color{blue}{ab}\color{orange}{abc}\color{green}{ab}$$$. The $$$LCP(\color{red}{ab},\color{blue}{ab},\color{orange}{abc},\color{green}{ab})$$$ is $$$2$$$, since $$$ab$$$ is the Longest Common Prefix of those four strings. Note that each substring consists of a continuous segment of characters and each character belongs to exactly one substring.

Your task is to find $$$f_l,f_{l+1},\dots,f_r$$$. In this version $$$l=r$$$.

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

The first line of each test case contains two integers $$$n$$$, $$$l$$$, $$$r$$$ ($$$1 \le l = r \le n \le 2 \cdot 10^5$$$) — the length of the string and the given range.

The second line of each test case contains string $$$s$$$ of length $$$n$$$, all characters are lowercase English letters.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2\cdot 10^5$$$.

Output format:
For each test case, output $$$r-l+1$$$ values: $$$f_l,\dots,f_r$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first sample $$$n=k$$$, so the only division of $$$aba$$$ is $$$\color{red}a\color{blue}b\color{orange}a$$$. The answer is zero, because those strings do not have a common prefix.

In the second sample, the only division is $$$\color{red}a\color{blue}a\color{orange}a$$$. Their longest common prefix is one.

Example input:
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

Example output:
0
1
3
2
10
2
0

Editorial:
Consider $$$F_{\ell}$$$ is a function which returns true iff it is possible to divide the string into at least $$$k$$$ segments with their LCP equal to $$$\ell$$$. Notice that $$$F_{\ell}$$$ implies $$$F_{\ell - 1}$$$ for $$$\ell > 0$$$. So we may find the maximal $$$\ell$$$ using binary search, which will be the answer for the problem.
How to compute $$$F_{\ell}$$$? Let us find Z-function $$$z_1,\dots,z_n$$$ of the given string. Notice that in the division $$$w_1,\dots,w_k$$$ we have $$$w_1$$$ as the prefix of the given string and all the strings have the common prefix with $$$w_1$$$ of length $$$\ell$$$. Notice that $$$z_p$$$ gives us the longest common prefix with $$$w_1$$$ and a segment starting at $$$p$$$. So if $$$z_p\geq \ell$$$ we may take this segment into account. In such greedy approach we count the maximal number of segments we can divide our string into. If this number is at least $$$k$$$, then $$$F_{\ell}$$$ is true.
The complexity is $$$O(n\log n)$$$.