解题思路
本题要求从所有起始片段的整理后片段中按字典序找出第 k 小的那一个。直接生成所有整理后片段并排序的复杂度太高，需要利用计数的思路进行比较和排序。
-
预处理前缀计数
设 cnt[i][d] 表示字符串 s 的前 i 个字符中，字母 'a'+d 出现的次数。同时维护 max_letter[i]，表示前 i 个字符中出现过的最大的字母索引（'a' 为 0，'z' 为 25）。该数组可以在线性时间内递推求得。
-
自定义比较函数（整理后片段 ti 与 tj 的字典序比较）
由于整理后片段是将对应起始片段（前缀）内部字符按 a 到 z 排序后得到的，因此其结构可以仅用计数数组表示。比较时，从 'a' 到 'z' 依次考虑每个字母 d：
题目内容
考古学家发现了一块刻有神秘文字的石板，上面是一个仅由小写字母组成的串。为了解读信息，他需要按照一种特殊的流程重新整理该串的所有“起始片段”。
具体来说，对于一个长度为 n 的串 s，定义它的 n 个起始片段依次为 s 的前 1,2,…,n 个字符构成的子串。接下来进行两步操作：首先，对每一个起始片段，将其内部的字母按照从 'a' 到 'z' 的自然顺序从小到大重新排列，得到该片段的“整理后片段”；然后，将所有 n 个整理后片段按照标准比较顺序从小到大排序。标准比较顺序定义如下：从两个片段的第一个字符开始逐个比较，直到找到第一个不同的字符，字符在自然顺序中更靠前（'a' 最小，'z' 最大）的片段的顺序靠前；若一直比较到其中一个片段的末尾仍相同，则较短的片段的顺序靠前。
现在，考古学家想知道，排序完成后的整理后片段中，排在第 k 小的那一个是什么。请帮助他求出结果。
约束：字符串长度 n 满足 1≤n≤2×105，k 满足 1≤k≤n。测试用例的数量 T 不超过 100，且所有测试用例的 n 之和不超过 2×105。
