swordx's blog

lexicographically smallest rotated sequence problem
By swordx, history, 7 years ago, In English

Hi All,

Can someone share their ideas on how to do the following problem in O(n): http://www.geeksforgeeks.org/lexicographically-smallest-rotated-sequence-set-2/

I have found on wikipedia that it can be done in O(n). I am not able to understand the booth's algorithm given on wikipedia.

Can someone share their approach to solve this problem in O(n).

Thanks in advance

  • Vote: I like it
  • +3
  • Vote: I do not like it

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What if you concatenate the input sequence with itself, then compute the suffix tree of that. The answer should be the least suffix that starts in the original sequence.

Not entirely sure that's true, I could have missed a corner case or it could just be totally broken. But it sounds plausible to me.

You can of course use suffix arrays instead, though the linear-time suffix array constructions I've seen are fairly advanced.

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Old TopCoder thread with discussion on this problem

→ Reply
»
7 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Double your string s. Now you have string a, that contains every cyclic shift of s as substring. Now build suffix automata on a. Now just start in root vertex and go |s| times chosing edge with minimal letter on it. It actually O(nlog|alph|), where |alph| is alphabet size, but log 26 is small, so it's O(n)

→ Reply