Minimum Lexicographic Rotation Using Suffix Array
algorithm, suffix-array
Solution
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.
Problem
``` 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!!