No.2858 Make a Palindrome
タグ : / 解いたユーザー数 41
作問者 :
Problem Statement
You are given $T$ test cases. Solve the following problem for each of them.
You are given a string $S$ of length $N$.
You have an empty string $U$, and you may perform the following operation any number of times.
- Concatenate $S$ to $U$. That is, replace $U$ with $U S$.
Find the minimum number of operations required for the contiguous substrings of the string $U$ to include a palindrome of length at least $M$.
If this cannot be achieved no matter how many operations are performed, output -1.
Constraints
- $1 \leq T \leq 2 \times 10^{5}$
- $1 \leq N \leq 2 \times 10^{5}$
- $1 \leq M \leq 10^{9}$
- $S$ is a string of length $N$ consisting of lowercase English letters.
- For the test cases contained in $1$ input, the sum of $N$ is at most $2 \times 10^{5}$.
- $T, N, M$ are integers.
Input
The input is given from Standard Input in the following format.
$T$
$\text{case}_1$
$\vdots$
$\text{case}_T$
Each test case is given in the following format.
$N$ $M$ $S$
Output
Output $T$ lines. On the $i$-th line, output the answer to the problem for the $i$-th test case.
Sample
Sample 1
Input
3 4 10 acbc 3 2357 aba 4 2 sepa
Output
3 786 -1
For the $1$st test case, performing the operation $3$ times gives $U = $ acbcacbcacbc, which contains cbcacbcacbc, a palindrome of length $11$, as a contiguous substring.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。