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的问题。其他用户已经在堆栈流中提出了此问题。[但是，这并没有用，我想通过后缀Array来解决。

如何使用后缀数组解决此问题？

直到现在我做了什么？？

（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}。

我还计算了每个后缀b / w的LCP [尽管我不确定在这个问题上我会需要它]。

现在 如何进一步进行。如何使用SA获得理想的结果？

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

谢谢！！