Factorize string into Lyndon words
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']