Lyndon word: Difference between revisions
Jump to navigation
Jump to search
mNo edit summary |
|||
| (One intermediate revision by the same user not shown) | |||
| Line 1: | Line 1: | ||
A '''Lyndon word''' is a word that is lexicographically strictly less than all of its rotations. (A Lyndon word must be [[primitive]] by definition.) | A '''Lyndon word''' is a nonempty word that is lexicographically strictly less than all of its other rotations. (A Lyndon word must be [[primitive]] by definition.) | ||
== Algorithm == | == Algorithm == | ||
Latest revision as of 02:34, 2 September 2024
A Lyndon word is a nonempty word that is lexicographically strictly less than all of its other 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.