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

Question

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

因为S = 'abaeb',轮换可以'baeba'

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

答案必须排除琐碎的矩阵行排序.

Answer 1

编辑:贾斯汀皮尔指出

只需将字符串附加到自身bbaeb就可以了bbaebbbaeb(对于涉及字符串旋转的问题,这是一个方便的技巧).
查找后缀数组.
遍历它并仅选择小于orignal 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数组在O(n)时间复杂度下解决它.基本上字符串的后缀数组包含字典顺序中字符串的所有后缀的索引.
对于字符串abaeb,字典顺序中的后缀为:

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

所以后缀数组 S=02413

具有O(n log ^ 2n)时间复杂度的代码在该链接处给出,具有详细说明,并且下一页具有针对O(n)的优化.如果您想保持代码简单,那么使用已经回答的比较运算符是关键.如果您主要关心的是效率,那么使用o(n)后缀数组构造.