O. 子串的字典序 II

传统题

1000ms

256MiB

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

翻译自 CSES-2109 题。

给定一个长度为 $n$ 的字符串。将其所有子串（不一定是不同的）按字典序排序，求出第 $k$ 个最小的子串。

第一行输入一个长度为 $n$ 的字符串，字符串中的字符是小写字母 $a–z$ 。

第二行输入一个整数 $k$ 。

输出第 $k$ 个最小的不同子串（按字典序排序）。

baabaa
10

ab

按字典序排序，前 $10$ 个最小的子串是：a, a, a, a, aa, aa, aab, aaba, aabaa 和 ab。因此，第 $10$ 个最小的子串是 "ab"。

$1 \leq n \leq 10^5$ ；

$1 \leq k \leq \frac{n(n+1)}{2}$ ，并且保证 $k$ 不会超过不同子串的总数。