N - Shortest Container Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

問題文

長さ N の英小文字からなる文字列 S が与えられます。

S を部分文字列として K 箇所含むような英小文字からなる文字列のうち長さが最小の文字列の長さを求めてください。

ただし、部分文字列とは連続する部分列のことを指します。例えば、xxx は yxxxy の部分文字列ですが、xxyxx の部分文字列ではありません。

制約

  • 1 \leq N \leq 5 \times 10^5
  • 1 \leq K \leq 10^9
  • S は英小文字からなる長さ N の文字列である

入力

入力は以下の形式で標準入力から与えられる。

N K
S

出力

答えを出力せよ。

入力例 1

7 2
strings

出力例 1

13

strings を部分文字列として 2 箇所含むような文字列には stringstrings があり、長さは 13 です。また、長さ 12 以下の文字列で条件を満たすものは存在しないため、答えは 13 です。

入力例 2

5 30
abcab

出力例 2

92

Problem Statement

You are given a string S of length N consisting of lowercase English letters.

Find the minimum length of a string consisting of lowercase English letters that contains S as a substring at least K times.

Here, a substring refers to a (consecutive) subarray. For example, xxx is a substring of yxxxy, but not of xxyxx.

Constraints

  • 1 \leq N \leq 5 \times 10^5
  • 1 \leq K \leq 10^9
  • S is a string of length N consisting of lowercase English letters.

Input

The input is given from Standard Input in the following format:

N K
S

Output

Print the answer.

Sample Input 1

7 2
strings

Sample Output 1

13

The string stringstrings of length 13 contains strings as a substring twice. No string of length 12 or less satisfies the condition, so the answer is 13.

Sample Input 2

5 30
abcab

Sample Output 2

92