algorithm - 使用后缀数组的最小字典序旋转

Question

    Consider a string of length n (1 <= n <= 100000). 
    Determine its minimum lexicographic rotation. 
    For example, the rotations of the string “alabala” are:

    alabala

    labalaa

    abalaal

    balaala

    alaalab

    laalaba

    aalabal

    and the smallest among them is “aalabal”.

这是 ACM ICPC 2003 的问题。这个问题已经被一些其他用户在堆栈流中问过。[但那没有用，因为我想通过后缀数组来完成。]

如何使用后缀数组来解决这道题？

到现在为止我做了什么？？

(1) 假设给定的字符串是 S。

我将字符串 S 与其自身连接起来得到一个字符串 S'。

即。 S'=S+S.

(2).然后我在O(nlog n )时间内找到了S'的后缀数组。

For example:
    S=alabala
    S'=alabalaalabala

Suffix No. Index    Suffixes

0       13      a
1       6       aalabala
2       9       abala
3       2       abalaalabala
4       11      ala
5       4       alaalabala
6       7       alabala
7       0       alabalaalabala
8       10      bala
9       3       balaalabala
10      12      la
11      5       laalabala
12      8       labala
13      1       labalaalabala

所以我算好了后缀数组SA，SA[]={13,6,9,2,11,4,7,0,10,3,12,5,8,1}。

我还计算了每个后缀的 LCP b/w [虽然我不确定我是否会在这个问题中需要它]。

现在如何进行下一步。如何使用SA得到想要的结果？

用一个非常*小的例子进行解释会非常有效。

谢谢!!

Answer 1

看来你应该取SA中的第一个后缀，它的索引在0和length(S) - 1之间。

一些解释:S 的所有旋转都在 S 后缀的开头，从 0 到 length(S) - 1 之间的位置。后缀数组按字典顺序保存后缀，所以你只需要选择第一个从S的旋转。