Lexicographically minimal string rotation: Difference between revisions

Revision as of 09:51, 24 February 2013

Revision as of 17:04, 26 October 2013

Line 17:

==Algorithms==

===The Naive Algorithm===

The naive algorithm for finding the lexicographically minimal rotation of a string is to iterate through successive rotations while keeping track of the most lexicographically minimal rotation encountered. If the string is of length '''''n''''', this algorithm runs in '''''O(n²)''''' time in the worst case.

Line 60 ⟶ 61:

===Shiloach's Fast Canonization Algorithm===

Shiloach (1981)<ref> {{cite journal

| title = Fast canonization of circular strings

| journal = Journal of Algorithms

Line 78 ⟶ 79:

===Duval's Lyndon Factorization Algorithm===

Duval (1983)<ref> {{cite journal

| title = Factorizing words over an ordered alphabet

| journal = Journal of Algorithms

Line 91 ⟶ 92:

| author = Jean Pierre Duval }}

</ref>

proposed an efficient algorithm involving the factorization of the string into its component [[Lyndon word|Lyndon words]]s, which runs in linear time with a constant memory requirement.

==Variants==