← 返回题目列表

Codeforces · 128/B

B. 字符串

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

有一天,安娜和玛丽亚在 IT 课上了解了词典顺序。

如果 x 是 y 的前缀(且 x ≠ y),或者存在这样的 i (1 ≤ i ≤ min(|x|, |y|)),即 xi < yi,并且对于任何 j (1 ≤ j < i) xj = yj,则字符串 x 按字典顺序小于字符串 y。这里|一个|表示字符串a的长度。现代编程语言中字符串的字典序比较是通过运算符<来实现的。

老师给安娜和玛丽亚布置了作业。她给了他们一根长度为n的字符串。他们应该写出给定字符串的所有子字符串,包括整个初始字符串和相等的子字符串(例如,应该从字符串“aab”中写出以下子字符串:“a”,“a”,“aa”,“ab”,“aab”,“b”)。生成的字符串应按字典顺序排序。狡猾的老师并不想检查所有这些字符串。这就是为什么她说只从列表中查找第 k 个字符串。帮助安娜和玛丽亚做作业。

输入

第一行包含一个仅由小拉丁字母(“a”-“z”)组成的非空字符串,其长度不超过105。第二行包含唯一的整数k(1≤k≤105)。

输出

打印 Anna 和 Maria need 的字符串 — 给定字符串的第 k 个(按字典顺序)子字符串。如果子字符串总数小于 k,则打印一个字符串“No such line”。 (不带引号)。

示例

输入 #1

aa
2

输出 #1

a

输入 #2

abc
5

输出 #2

bc

输入 #3

abab
7

输出 #3

b

注意

在第二个示例中,字符串“bc”之前跟随字符串“a”、“ab”、“abc”、“b”。