← 返回题目列表

Codeforces · 1537/E1

E1. 擦除和扩展(简易版)

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

这是问题的简单版本。唯一的区别是 $$$n$$$ 和 $$$k$$$ 的约束。只有当问题的所有版本都得到解决后,你才能进行黑客攻击。

你有一个字符串 $$$s$$$,你可以对其进行两种类型的操作:

- 删除字符串的最后一个字符。
- 复制字符串:$$$s:=s+s$$$,其中$$$+$$$ 表示串联。

每个操作可以使用任意次(可能没有)。

你的任务是找到长度恰好为 $$$k$$$ 的按字典顺序最小的字符串,该字符串可以通过对字符串 $$$s$$$ 执行这些操作来获得。

当且仅当满足以下条件之一时,字符串 $$$a$$$ 按字典顺序小于字符串 $$$b$$$:

- $$$a$$$ 是 $$$b$$$ 的前缀,但 $$$a\ne b$$$;
- 在 $$$a$$$ 和 $$$b$$$ 不同的第一个位置,字符串 $$$a$$$ 在字母表中的某个字母比 $$$b$$$ 中的对应字母更早出现。

输入

第一行包含两个整数 $$$n$$$、$$$k$$$ ($$$1 \leq n, k \leq 5000$$$) — 原始字符串 $$$s$$$ 的长度和所需字符串的长度。

第二行包含字符串$$$s$$$,由$$$n$$$小写英文字母组成。

输出

打印按字典顺序排列的长度为 $$$k$$$ 的最小字符串,该字符串可以通过对字符串 $$$s$$$ 进行操作来获得。

示例

输入 #1

8 16
dbcadabc

输出 #1

dbcadabcdbcadabc

输入 #2

4 5
abcd

输出 #2

aaaaa

注意

在第一个测试中,最好进行一个重复:“dbcadabc”$$$\to$$$“dbcadabcdbcadabc”。

在第二个测试中,最好删除最后 $$$3$$$ 字符,然后重复字符串 $$$3$$$ 次,然后删除最后 $$$3$$$ 字符以使字符串长度为 $$$k$$$。

"abcd" $$$\to$$$ "abc" $$$\to$$$ "ab" $$$\to$$$ "a" $$$\to$$$ "aa" $$$\to$$$ "aaaa" $$$\to$$$ "aaaaaaaa" $$$\to$$$ "aaaaaaa" $$$\to$$$“aaaaaa”$$$\to$$$“aaaaa”。