Minimum Lexicographic Rotation Using Suffix Array

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”.

This is the problem from ACM ICPC 2003 .This problem has already been asked in stack flow by some other user.[But that wasn't useful as , I want to do it by suffix Array.]

How to do this problem using the Suffix Array?

Till Now what I had done??

(1) Lets say the given string is S.

I concatenated the string S with itself to get a string S'.

ie. S'=S+S.

(2).Then I found the suffix array of S' in O(nlog n )time.

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

So I calculated the suffix-array SA well ,SA[]={13,6,9,2,11,4,7,0,10,3,12,5,8,1}.

Also I calculated the LCPs b/w every suffixes [Although i am not confident that I will require it in this problem].

Now How to proceed further.How to use SA to get a desired result?

Explanation with a very *small example will be quite effective.

Thanks!!

Answer 1

It seems that you should take first suffix in SA, which index is between 0 and length(S) - 1.

Some explanation: all rotations of S are in the beginning of S' suffixes from positions between 0 and length(S) - 1. Suffix array keeps suffixes in lexicographical order, so you just need to pick the first one which begins from rotation of S.