Background

TJOI2019 D2T2.

Source file name: substring.*.

Time limit: 1 s. Memory limit: 128 MB.

Problem Description

Striker has a string of length $n$. He only knows that one of its substrings is the password to a family treasure passed down from his ancestors. But since the string is very long, it is hard for Striker to try all substrings one by one.

One day, Striker went to Mr. Toluene for fortune-telling, but Mr. Toluene said: “Heaven’s secrets must not be revealed.”

After Striker’s repeated pleas, Mr. Toluene told him: “The password is a substring that appears exactly $k$ times in the string.”

But Striker still did not know what to do. After even more pleading, Mr. Toluene, seeing his sincerity, added: “Among the substrings that appear exactly $k$ times, classify them by substring length. The password is in the length group with the largest count.”

To try the password, Striker wants you to help find the length value whose count is the largest among substrings that appear $k$ times (if there are multiple answers, output the longest length).

Input Format

The first line contains a positive integer $T$, meaning there are $T$ test cases.

In the next $T$ lines, each line contains a string and a positive integer $k$.

Output Format

Output $T$ lines in total. Each line contains one integer: among substrings that appear exactly $k$ times, output the length that has the largest number of such substrings. If no substring appears exactly $k$ times, output $-1$.

6
aab 1
abc 1
aaaa 2
abab 2
ababacc 2
abab 4

2
1
3
1
2
-1

Hint

Data Explanation

For the first test case: the substrings $b, aa, ab, aab$ all appear once. Among them, substrings of length $1$ appear $1$ time, length $2$ appear $2$ times, and length $3$ appear $1$ time. So the answer is $2$.

For the second test case: the substrings $a, b, c, ab, bc, abc$ all appear once. Among them, substrings of length $1$ appear $3$ times, length $2$ appear $2$ times, and length $3$ appear $1$ time. So the answer is $1$.

For the third test case: the substring $aaa$ appears twice. Substrings of length $3$ appear $1$ time, and there are none for all other lengths. So the answer is $3$.

For the fourth test case: the substrings $a, b, ab$ appear twice. Among them, substrings of length $1$ appear $2$ times, and length $2$ appear $1$ time. So the answer is $1$.

For the fifth test case: the substrings $b, c, ab, ba$ appear twice. Among them, substrings of length $1$ appear $2$ times, and length $2$ appear $2$ times. So the answer is $2$.

For the sixth test case: no substring appears four times. So the answer for this problem is $-1$.

Constraints

For $20\%$ of the testdata, $1 \leq k \leq n \leq 10$.

For $100\%$ of the testdata, $1 \leq n \leq 10^5$, $1 \leq T \leq 100$, $\sum n \leq 3 * 10^6$. The input strings contain only lowercase English letters.

Translated by ChatGPT 5