G1. Division + LCP (easy version)
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\).
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\).
For each test case, output \(r-l+1\) values: \(f_l,\dots,f_r\).
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.