algorithm - 如何在不使用矩阵的情况下对字符串旋转进行排序

Question

我想对字符串的旋转进行排序。
例如:

对于 S = 'abaeb'，旋转可以是 'baeba'

我需要获取 S 的索引列表，按字典顺序排序。
在我们的示例中:V = 02413。

答案必须排除平凡的矩阵行排序。

Answer 1

编辑:由 Justin Peel 指出

只需将字符串附加到自身 bbaeb 就变成了 bbaebbbaeb(解决涉及字符串旋转问题的便捷技巧)。
查找后缀数组。
遍历它，只选择小于原始 string(5) 长度的值。上述字符串的后缀数组

aeb  7
aebbbaeb  2
b  9
baeb  6
baebbbaeb 1
bbaeb 5
bbaebbbaeb 0
eb  8
ebbbaeb  3

S = 7 2 7 6 1 5 0 4 8 3

现在遍历 Ans= 2 1 0 4 3

编辑结束

您可以使用 Suffix array 以 O(n) 的时间复杂度解决它.基本上，字符串的后缀数组包含按字典顺序排列的字符串的所有后缀的索引。
对于字符串abaeb，其后缀按字典序为:

abaeb (0)
aeb   (2)
b     (4) 
baeb  (1)
e     (3)

所以后缀数组S=02413

该链接给出了时间复杂度为 O(n log^2n) 的代码并提供了详细说明，下一页对 O(n) 进行了优化。如果您想保持代码简单，那么使用已经回答过的比较运算符是关键。如果您主要关心的是效率，则使用 o(n) 后缀数组构造。