# Smallest lexicographical rotation of a string using suffix arrays in O(n)

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:

alabala

labalaa

abalaal

balaala

alaalab

laalaba

aalabal

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!

-
How do you define "minimum"? What is the metric used (maybe it is obvious but I am not an expert)? – Giorgio Jan 1 '12 at 17:51
Thanks for the note! I thought the rotation had to be minimal (minimum offset), not the result of the rotation wrt lexicographical order. – Giorgio Jan 1 '12 at 19:55
I am still missing something: is the construction and sorting of the suffix array included in the complexity? I imagine it takes more than O(n) to construct the array and sort it. – Giorgio Jan 1 '12 at 23:35
I think the idea of repeating the original string twice is great! Then you can build the suffix array in O(2n) = O(n). But don't you need to sort it to find the minimum? This needs more than O(n), right? – Giorgio Jan 2 '12 at 12:21
@Giorgio well, the suffix array itself holds the suffices already sorted. And another note, maybe slightly offtopic - don't forget that sorting can be done even in o(n) with some assumptions to the objects sorted(check out the radix sort for example) – Tomy Jan 2 '12 at 14:38

A simple trick to construct all rotations of a string of length N is to concatenate the string with itself.

Then every N-length substring of this 2N-length string is a rotation of the original string.

Locating the "lexicographically minimal" substring is then done with your O(N) tree construction.

-

I'm pretty sure the information contained in a suffix array is not sufficient to help you get to O(n), but at most can help you to O(n log n). Consider this family of suffixes:

a
aba
abacaba
...

You construct the next suffix by taking the previous suffix (say aba), adding the next character not yet used and then adding the previous suffix again (so aba -> aba c aba).

Now consider these strings (the space is added for emphasis, but is not part of the string):

bd abacaba
cd abacaba

For these three strings, the start of the suffix array will look like this:

a
aba
abacaba
(other suffixes)

Looks familiar? These strings of course is tailored to create this suffix array. Now, depending on the starting letter (a, b or c), the 'correct' index (the solution to your problem) is either the first, the second or the third suffix in the list above.

The choice of the first letter hardly affects the suffix array; in particular, it does not affect the order of the first three suffixes in the suffix array. This means that we have log n strings for which the suffix array is extremely similar but the 'correct' index is very different.

Although I have no hard proof, this strongly suggests to me that you have no choice but to compare the rotations corresponding to these first three indices in the array for their lexicographic ordering, which in turn means that you'll need at least O(n log n) time for this (as the number of alternative first characters - in our case 3 - is log n, and comparing two strings takes O(n) time).

This does not rule out the possibility of an O(n) algorithm. I merely have doubts that a suffix array helps you in achieving this running time.

-

The smallest rotation is the one that start with some of the suffix from the suffix array. Suffixes are lexicographically ordered. This gives you a big jumpstart:

• you know that once you get such k that rotation starting with suffix k is smaller than rotation starting with suffix k+1, you're done (starting from the first one);
• you can do the comparision of "rotation starting with suffix k is smaller than rotation starting with suffix k+1" in O(1) by comparing lengths of suffixes and optionally, comparing one character with one another character.

EDIT: "one character with one another character" may not always be so, it may be more than one character, but overall, you do not examine more than n characters through the whole search process, so it is O(n).

Short proof: You only examine characters when suffix k+1 is longer than suffix k, and you stop and found your solution if suffix k+1 is shorter than suffix k (then you know suffix k is the one you sought for). So you only examine characters while you are in rising (length-wise) sequence of suffixes. Since you only examine excess characters, you cannot examine more than n characters.

EDIT2: This algorithm relies on the fact the "if there are two neighbour suffixes in suffix array and the previous is shorter than the subsequent, the previous is prefix of the subsequent". If this is not true, then sorry.

EDIT3: No, it does not hold. "abaaa" has suffix table "a", "aa", "aaa", "abaaa", "baaa". But maybe this line of thought can ultimately lead to the solution, just some more details must be sophisticated more. The primary question is whether it is possible to somehow make the aforementioned comparision done by examining less characters, so it is O(n) totally, which I somehow believe may be possible. I just can't tell how, now.

-

I don't see anything better than O(N²).

If you have a list of N integers, you can pick the smallest in O(N) comparisons.

Here you have a list of N strings of size N (constructing them cost nothing, a string is fully determined by its starting index). You can pick the smallest in O(N) comparisons. But each comparison is O(N) basic operations. So the complexity is O(N²).

-