Factorize string into Lyndon words: Difference between revisions
Content deleted Content added
imported>CosmiaNebula No edit summary |
imported>CosmiaNebula mNo edit summary |
||
Line 3: | 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. |
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 [[ |
A [[Lyndon word]] is a non-empty string that is ''strictly'' lower in lexicographic order than all its circular rotations. In particular, if a string is equal to a circular rotation, then it is not a Lyndon word. For example, since 0101 = 0101 (rotation by 2), it is not a Lyndon word. |
||
⚫ | |||
⚫ | |||
: 0, 1, 01, 001, 011, 0001, 0011, 0111, 00001, 00011, 00101, 00111, 01011, 01111, ... |
: 0, 1, 01, 001, 011, 0001, 0011, 0111, 00001, 00011, 00101, 00111, 01011, 01111, ... |
||
Some basic properties: |
|||
* The only Lyndon word that ends with 0 is 0. |
* The only Lyndon word that ends with 0 is 0. |