← 返回题目列表

AtCoder · past22_n

N. 最短的集装箱

中文机器翻译题面 查看原题

问题陈述

给你一个字符串 S 长度 N 由小写英文字母组成。

求由小写英文字母组成的字符串的最小长度,其中包含 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

字符串 stringstrings 长度 13 包含 strings 作为子字符串两次。 没有长度的字符串 12 或更少满足条件,所以答案是 13.


示例输入 2

5 30
abcab

示例输出 2

92