Factorize string into Lyndon words: Difference between revisions
Content added Content deleted
imported>CosmiaNebula (description of problem) |
imported>CosmiaNebula (citation) |
||
| Line 12: | Line 12: | ||
* '''Proof.''' For, the only way for two different strings s, s' to have the same lexicographic ordering is for one of them to pad to the other. We can assume that s00...0 = s'. If that is so, then s00...0 is a Lyndon word that ends with 0, so it is just 0, and so s is a Lyndon word that is also empty, contradiction. |
* '''Proof.''' For, the only way for two different strings s, s' to have the same lexicographic ordering is for one of them to pad to the other. We can assume that s00...0 = s'. If that is so, then s00...0 is a Lyndon word that ends with 0, so it is just 0, and so s is a Lyndon word that is also empty, contradiction. |
||
The Chen–Fox–Lyndon theorem states that any string is uniquely factorizable into a sequence of Lyndon words non-decreasing in lexicographic order. Duval's algorithm computes this in O(length of input) time and and O(1) space.<ref>Duval, Jean-Pierre (1983), "Factorizing words over an ordered alphabet", ''Journal of Algorithms'', '''4''' (4): 363–381, doi:10.1016/0196-6774(83)90017-2</ref>{{task}} |
The Chen–Fox–Lyndon theorem states that any string is uniquely factorizable into a sequence of Lyndon words non-decreasing in lexicographic order. Duval's algorithm computes this in O(length of input) time and and O(1) space.<ref>Duval, Jean-Pierre (1983), "Factorizing words over an ordered alphabet", ''Journal of Algorithms'', '''4''' (4): 363–381, doi:10.1016/0196-6774(83)90017-2</ref> See <ref>https://cp-algorithms.com/string/lyndon_factorization.html</ref> for a description of Duval's algorithm.{{task}} |
||
== [[Python]] == |
== [[Python]] == |
||
<syntaxhighlight lang="python3"> |
Duval's algorithm:<syntaxhighlight lang="python3"> |
||
def chen_fox_lyndon_factorization(s): |
def chen_fox_lyndon_factorization(s): |
||
n = len(s) |
n = len(s) |
||