题目描述

给定一个字符串 $s$。请输出 $s$ 的所有不同的子串中，按字典序排列的第 $K$ 小的子串。

这里，$s$ 的子串指的是从 $s$ 中取出的非空连续部分组成的字符串。例如，若 $s = \texttt{ababc}$，则 $\texttt{a}$、$\texttt{bab}$、$\texttt{ababc}$ 都是 $s$ 的子串，而 $\texttt{ac}$、$\texttt{z}$、空字符串都不是 $s$ 的子串。不同的子串是指作为字符串内容不同。

此外，设 $X = x_1x_2...x_n$，$Y = y_1y_2...y_m$ 是两个不同的字符串。当 $Y$ 是 $X$ 的前缀，或者存在最小的整数 $j$ 使得 $x_j \neq y_j$ 且 $x_j > y_j$ 时，只有在这种情况下才认为 $X$ 的字典序大于 $Y$。

输入格式

输入从标准输入中给出，格式如下：

$s$ $K$

输出格式

请输出 $s$ 的所有不同子串中，按字典序排列的第 $K$ 小的子串。

样例 1

输入

aba
4

输出

b

样例 2

输入

atcoderandatcodeer
5

输出

andat

样例 3

输入

z
1

输出

z

说明/提示

限制条件

• $1 \leq |s| \leq 5000$
• $s$ 仅由小写英文字母组成
• $1 \leq K \leq 5$
• $s$ 至少有 $K$ 个不同的子串

部分得分

• 若能正确解决 $|s| \leq 50$ 的数据集，可获得部分分 $200$ 分。

样例说明 1

$s$ 的子串有 $\texttt{a}$、$\texttt{b}$、$\texttt{ab}$、$\texttt{ba}$、$\texttt{aba}$ 共 $5$ 个。请输出其中按字典序排列第 $4$ 小的 $\texttt{b}$。注意不要重复计数 $\texttt{a}$。

由 ChatGPT 4.1 翻译