← 返回题目列表

AtCoder · arc097_a

C. 第 K 个子串

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

分数: 300 点

问题陈述

给你一个字符串 s。 其中 不同 的子串 s,打印 K- 字典顺序最小的一个。

的子串 s 是取出其中非空连续部分得到的字符串 s。 例如,如果 s = ababc, a, bab 和 ababc 是子串 s,同时 ac, z 和空字符串不是。 另外,当子串与字符串不同时,我们就说子串是不同的。

让 X = x_{1}x_{2}...x_{n} 和 Y = y_{1}y_{2}...y_{m} 是两个不同的字符串。 X 按字典顺序大于 Y 当且仅当 Y 是前缀 X or x_{j} > y_{j} 其中 j 是满足以下条件的最小整数 x_{j} \neq y_{j}.

约束

  • 1 ≤ |s| ≤ 5000
  • s 由小写英文字母组成。
  • 1 ≤ K ≤ 5
  • s 至少有 K 不同的子字符串。

部分分数

  • 200 分数将作为通过满足以下条件的测试集的部分分数授予: |s| ≤ 50.

输入

输入由标准输入按以下格式给出:

s
K

输出

打印 K- 按字典顺序排列的最小子串 K.


示例输入 1

aba
4

示例输出 1

b

s 有五个子字符串: a, b, ab, ba 和 aba。 其中,我们应该打印第四小的, b。 请注意,我们不计算 a 两次。


示例输入 2

atcoderandatcodeer
5

示例输出 2

andat

示例输入 3

z
1

示例输出 3

z