6891 - Substring Order II

6891.Substring Order II

Time Limit: 1s Memory Limit: 512MB

You are given a string of length $n$ . If all of its substrings (not necessarily distinct) are ordered lexicographically, what is the $k$ th smallest of them?

Input Format(From the terminal/stdin)

The first input line has a string of length $n$ that consists of characters a–z.

The second input line has an integer $k$ .

$1 \le n \le 10^5$
$1 \le k \le \frac{n(n+1)}{2}$

Output Format(To the terminal/stdout)

Print the $k$ th smallest substring in lexicographical order.

Sample Input

Copy

baabaa
10
      \n
  \n

Sample Output

Copy

ab
  \n

The 10 smallest substrings in order are a, a, a, a, aa, aa, aab, aaba, aabaa, and ab.

Source: CSES, String Algorithms, 2109

Submit

请先登录

Submit

题解(0)