Factorize string into Lyndon words: Difference between revisions
Content added Content deleted
imported>CosmiaNebula (starting up) |
imported>CosmiaNebula (python code) |
||
Line 1: | Line 1: | ||
{{task}} |
{{task}} |
||
== [[Python]] == |
|||
<syntaxhighlight lang="python3"> |
|||
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 |
|||
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)) |
|||
... |
|||
</syntaxhighlight> |
|||
Examples |
Revision as of 21:29, 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
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))