I will quote the problem from ACM 2003:
Consider a string of length n (1 <= n <= 100000). Determine its minimum lexicographic rotation. For example, the rotations of the string “alabala” are:
and the smallest among them is “aalabal”.
As for the solution - I know I need to construct a suffix array - and let's say I can do that in O(n). My question still is, how can I find the smallest rotation in O(n)? (n=length of a string)
I'm very interested in this problem and still I somehow don't get the solution. I'm more interested in the concept and how to solve the problem and not in the concrete implementation.
Note: minimum rotation means in the same order as in an english dictionary - "dwor" is before "word" because d is before w.
EDIT: suffix array construction takes O(N)
LAST EDIT: I think I found a solution!!! What if I just merged two strings? So if the string is "alabala" the new string would me "alabalaalabala" and now I'd just construct a suffix array of this (in O(2n) = O(n)) and got the first suffix? I guess this may be right. What do you think? Thank you!