Factorize string into Lyndon words: Difference between revisions
Content added Content deleted
imported>CosmiaNebula (python code) |
imported>CosmiaNebula (→Python: finished) |
||
Line 20: | Line 20: | ||
assert ''.join(factorization) == s |
assert ''.join(factorization) == s |
||
return factorization |
return factorization |
||
</syntaxhighlight>'''Example use with [[Thue-Morse|Thue-Morse sequence]]'''<syntaxhighlight lang="python3"> |
|||
m='0' |
m='0' |
||
for i in range(0,7): |
for i in range(0,7): |
||
Line 30: | Line 30: | ||
print(chen_fox_lyndon_factorization(m)) |
print(chen_fox_lyndon_factorization(m)) |
||
</syntaxhighlight>'''Output:'''<syntaxhighlight lang="text"> |
|||
['011', '01', '0011', '00101101', '0010110011010011', '00101100110100101101001100101101', '001011001101001011010011001011001101001100101101', '001011001101', '001'] |
|||
</syntaxhighlight> |
</syntaxhighlight> |
Revision as of 21:31, 30 January 2024
Factorize string into Lyndon words
You are encouraged to solve this task according to the task description, using any language you may know.
You are encouraged to solve this task according to the task description, using any language you may know.
Python
def chen_fox_lyndon_factorization(s):
n = len(s)
i = 0
factorization = []
while i < n:
j, k = i + 1, i
while j < n and s[k] <= s[j]:
if s[k] < s[j]:
k = i
else:
k += 1
j += 1
while i <= k:
factorization.append(s[i:i + j - k])
i += j - k
assert ''.join(factorization) == s
return factorization
Example use with Thue-Morse sequence
m='0'
for i in range(0,7):
m0=m
m=m.replace('0','a')
m=m.replace('1','0')
m=m.replace('a','1')
m=m0+m
print(chen_fox_lyndon_factorization(m))
Output:
['011', '01', '0011', '00101101', '0010110011010011', '00101100110100101101001100101101', '001011001101001011010011001011001101001100101101', '001011001101', '001']