Lexicographically minimal string rotation: Difference between revisions

Revision as of 03:49, 19 January 2016

Revision as of 22:58, 20 January 2016

Line 73:

| author = Yossi Shiloach }}

</ref>

proposed an algorithm improving on Booth's result in terms of performance. It was observed that if there are {{mvar|'''''q}}''''' equivalent lexicographically minimal rotations of a string of length {{mvar|'''''n}}''''', then the string must consist of {{mvar|''q}}'' equal substrings of length {{tmath|1='''''d=n/q}}'''''. The algorithm requires only {{tmath|'''''n + d/2}}''''' comparisons and constant space in the worst case.

The algorithm is divided into two phases. The first phase is a quick sieve which rules out indices that are obviously not starting locations for the lexicographically minimal rotation. The second phase then finds the lexicographically minimal rotation start index from the indices which remain.