C - K-th Substring 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 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 ≤ |s| ≤ 5000
  • s は英小文字からなる
  • 1 ≤ K ≤ 5
  • s は異なる substring を K 個以上持つ

部分点

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

入力

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

s
K

出力

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

入力例 1

aba
4

出力例 1

b

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

入力例 2

atcoderandatcodeer
5

出力例 2

andat

入力例 3

z
1

出力例 3

z

Score : 300 points

Problem Statement

You are given a string s. Among the different substrings of s, print the K-th lexicographically smallest one.

A substring of s is a string obtained by taking out a non-empty contiguous part in s. For example, if s = ababc, a, bab and ababc are substrings of s, while ac, z and an empty string are not. Also, we say that substrings are different when they are different as strings.

Let X = x_{1}x_{2}...x_{n} and Y = y_{1}y_{2}...y_{m} be two distinct strings. X is lexicographically larger than Y if and only if Y is a prefix of X or x_{j} > y_{j} where j is the smallest integer such that x_{j} \neq y_{j}.

Constraints

  • 1 ≤ |s| ≤ 5000
  • s consists of lowercase English letters.
  • 1 ≤ K ≤ 5
  • s has at least K different substrings.

Partial Score

  • 200 points will be awarded as a partial score for passing the test set satisfying |s| ≤ 50.

Input

Input is given from Standard Input in the following format:

s
K

Output

Print the K-th lexicographically smallest substring of K.

Sample Input 1

aba
4

Sample Output 1

b

s has five substrings: a, b, ab, ba and aba. Among them, we should print the fourth smallest one, b. Note that we do not count a twice.

Sample Input 2

atcoderandatcodeer
5

Sample Output 2

andat

Sample Input 3

z
1

Sample Output 3

z