Anonymous user
Factorize string into Lyndon words: Difference between revisions
Factorize string into Lyndon words (view source)
Revision as of 20:02, 2 February 2024
, 5 months agono edit summary
imported>CosmiaNebula No edit summary |
imported>CosmiaNebula mNo edit summary |
||
Line 3:
Given a finite alphabet, we can lexicographically order all strings in the alphabet. If two strings have different lengths, then pad the shorter string on the right with the smallest letter. For example, we have 01 > 001, but 01 = 010. As we see, this order is a total preorder, but not a total order, since it identifies different strings.
A [[
▲The first Lyndon words on the binary alphabet {0, 1} are:<blockquote>
: 0, 1, 01, 001, 011, 0001, 0011, 0111, 00001, 00011, 00101, 00111, 01011, 01111, ...
* The only Lyndon word that ends with 0 is 0.
|