6890.Substring Order I

Time Limit: 1s Memory Limit: 512MB

You are given a string of length $n$ . If all of its distinct substrings 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}$
  • It is guaranteed that $k$ does not exceed the number of distinct substrings.

Output Format(To the terminal/stdout)

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

Sample Input

Copy 
babaacbaab
10
          \n
  \n

Sample Output

Copy 
aba
   \n

The 10 smallest distinct substrings in order are a, aa, aab, aac, aacb, aacba, aacbaa, aacbaab, ab, and aba.

Source: CSES, String Algorithms, 2108

Submit

请先 登录
 Submit
题解(0)
© 2025 FAQs