链接: https://cses.fi/problemset/task/2108

板块: String Algorithms

时限: 1.00 s ｜ 内存: 512 MB

题目描述

给定一个长度为 $n$ 的字符串。如果将其所有不同的子串按字典序排列，其中第 $k$ 小的是哪一个？

输入

第一行输入包含一个由 a–z 字符组成、长度为 $n$ 的字符串。

第二行包含一个整数 $k$。

输出

输出按字典序第 $k$ 小的不同子串。

数据范围

$1 \le n \le 10^5$ $1 \le k \le \frac{n(n+1)}{2}$ 保证 $k$ 不超过不同子串的个数。

样例输入

babaacbaab
10

样例输出

aba