【文件属性】：
文件名称：leetcode第四题-Independent-Study:自学
文件大小：21KB
文件格式：ZIP
更新时间：2021-07-01 09:31:24
系统开源
leetcode
第四题独立学习
这项独立研究需要解决来自在线资源（包括
HackerRank、Leetcode
和
CodeChef）的各种难度的具有挑战性的算法问题。
这些问题的解决方案必须通过上述在线资源中提供的在线判断。
阿什顿和弦
问题陈述
Ashton
参加工作面试并被问到以下问题。
按字典顺序排列给定字符串的所有不同子字符串并将它们连接起来。
打印连接字符串的字符。
可以保证给定的值是有效的，即会有一个字符。
你能帮阿什顿解决这个问题吗？
例如，给定字符串
s=
abcd，其不同的子字符串是
[a,
ab,
abc,
abcd,
b,
bc,
bcd,
c,
cd,
d]。
排序和连接后，它们构成了字符串。
如果
k
=
5，则答案为
b，即
1
索引的连接字符串的第
5
个字符。
执行
这个问题的解决方案需要使用后缀数组和最长的公共前缀。
在找到不同的子字符串后，使用归并排序对字符串进行排序的最坏时间复杂度为
O(N$logN)。
为了改善这一点，可以使用后缀数组。
后缀字符串是字符串的一部分，可以使用索引进行排序。
举个例子：香蕉
指数
后缀
1
香蕉
2
安娜娜
3