#CS2108. 子串的字典序 I

子串的字典序 I

题目背景

翻译自 CSES-2108 题。

题目描述

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

输入格式

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

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

输出格式

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

样例

babaacbaab
10

aba

样例1解释 按字典序排序，前 101010 个最小的不同子串是：a, aa, aab, aac, aacb, aacba, aacbaa, aacbaab, ab 和 aba。因此，第 101010 个最小的子串是 "aba"。

说明/提示

$1 \leq n \leq 10^5$

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