#521. 「多校联考 Round 2」告别过去,拥抱未来

内存限制:512 MiB 时间限制:2000 ms 输入文件:future.in 输出文件:future.out
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

A shoulder for the past

给过往一个肩膀

Let out the cries imprisoned for so long

让久被禁锢的哭泣得以放声

A pair of wings for me at this moment

给此刻的自己一双翅膀

To soar above this world

翱翔于世界的上空

Turn into a shooting star that briefly shines but warms up every heart

化为一颗流星,给心灵一瞬的希望

May all the beauty be blessed

愿所有的美好都能得到祝福

—— 《Moon Halo》

给定一个长度为 n 字符串 s ,你可以进行以下两种操作:

A. 删去字符串的最后一个字符。

B. 将 s 变为 s+s ,即将这个字符串复制一倍接在末尾。

每种操作可以使用无限次。

你可以随意的进行操作,也可以不进行操作。

你需要找到 s 进行操作后获得的所有长度为 k 的字符串中字典序最小的字符串。

输入格式

future.in 中读入。

第一行两个整数 n,k ,意义如题目所述。

第二行一个字符串 s

输出格式

输出到 future.out 中。

一行一个字符串 ,表示答案。

样例

见附加文件中的 sample1.in/ans , sample2.in/ans , sampleBig.in/ans

样例解释

对于 sample1.in/ans 显然直接复制一倍最优。

对于 sample2.in/ans 显然将字符只删至剩下第一个字符,然后复制数次,最后删至剩下 k 个字符。

数据范围与提示

测试点 n \le k \le 特殊性质
1~4 5000 A
5~8 B
8~12 5 \times 10^4 \
13~16 5 \times 10^5 B
17~20 \

特殊性质

A 保证字符串s的最短循环节长度为1

B 保证字符串s的最短循环节长度为1000