配点 : $300$ 点

問題文

文字列 $s$ が与えられます。 $s$ の異なる substring のうち、辞書順で $K$ 番目に小さいものを出力してください。

ただし、$s$ の substring とは、 $s$ の空でない連続した部分を取り出してできる文字列とします。 例えば、 $s$ $=$ ababc とすると、 a, bab, ababc は $s$ の substring ですが、 ac, z, 空文字列 は $s$ の substring ではありません。 また、substring が異なるとは、文字列として異なることを指します。

なお、$X = x_{1}x_{2}...x_{n},$ $Y = y_{1}y_{2}...y_{m}$ を二つの異なる文字列とするとき、$Y$ が $X$ の接頭辞であるか、$j$ を $x_{j} \neq y_{j}$ であるような最小の整数として $x_{j} > y_{j}$ である場合、そしてその場合に限って $X$ は $Y$ より辞書順で大きいといいます。

制約

• $1$ $\leq$ $|s|$ $\leq$ $5000$
• $s$ は英小文字からなる
• $1$ $\leq$ $K$ $\leq$ $5$
• $s$ は異なる substring を $K$ 個以上持つ

部分点

• $|s|$ $\leq$ $50$ を満たすデータセットに正解した場合は、部分点として $200$ 点が与えられる。

入力

入力は以下の形式で標準入力から与えられる。

$s$

$K$

出力

辞書順で $K$ 番目に小さい $s$ の substring を出力せよ。

aba
4

b

$s$ の substring は a, b, ab, ba, aba の $5$ つです。 このうち $4$ 番目に小さい b を出力してください。 a を $2$ 回カウントしないことに注意してください。

atcoderandatcodeer
5

andat

z
1

z