Lyndon word: Difference between revisions
Jump to navigation
Jump to search
Created page with "A '''Lyndon word''' is a word that is lexicographically strictly less than all of its rotations. (A Lyndon word must be primitive by definition.) == Algorithm == The Lynd..." |
|||
| Line 2: | Line 2: | ||
== Algorithm == | == Algorithm == | ||
The Lyndon rotation of a primitive word can be found using Booth's algorithm in O(''n'') time where ''n'' is the length of a word. | The Lyndon rotation of a primitive word can be found using [https://doi.org/10.1016%2F0020-0190%2880%2990149-0 Booth's algorithm] in O(''n'') time where ''n'' is the length of a word. | ||
[[Category:Combinatorics on words]] | [[Category:Combinatorics on words]] | ||
Revision as of 02:32, 2 September 2024
A Lyndon word is a word that is lexicographically strictly less than all of its rotations. (A Lyndon word must be primitive by definition.)
Algorithm
The Lyndon rotation of a primitive word can be found using Booth's algorithm in O(n) time where n is the length of a word.