Here's a very important and basic problem in string:

Given a string S = s₁s₂s₃...s_l, define it's i-th rotation to be s_is_i+1...s_ls₁...s_i-1.

So for example, if S = "bacaa", it's five rotations are: "bacaa", "acaab", "caaba", "aabac", "abaca".

Now the question is simple: given the string S, find among its all rotations the lexicographically smallest one. In the above example where S = "bacaa", the answer is "aabac".

p.s. see if you can solve it without using sophisticated data structure like suffix array!