問題一覧 > 通常問題

No.2858 Make a Palindrome

レベル : / AI推定難易度 : 2000 / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 41
作問者 : dyktr_06 / テスター : square1001
お気に入りにしたユーザー ProblemId : 10860 / 自分の提出
問題文最終更新日: 2024-08-25 14:45:32
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 442 MMA Contest 019 (順位表) の他の問題:

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もしくは右上の雲マークをクリックしてアカウントを作成してください。