Duval's factorization
k ← -1
while k < n - 1 do
i ← k + 1
j ← k + 2
while j < n and wi ≤ wj do
if wi < wj then
i ← k + 1
else
i ← i + 1
j ← j + 1
while k < i do
output(k + 1)
k ← k + j - i
k ← -1
while k < n - 1 do
i ← k + 1
j ← k + 2
while j < n and wi ≤ wj do
if wi < wj then
i ← k + 1
else
i ← i + 1
j ← j + 1
while k < i do
output(k + 1)
k ← k + j - i
Details
- Reference: LYNDEX0001
- Brief description: this algorithm computes the Chen-Fox-Lyndon factorization of a word w of length n
- Author: Jean-Pierre Duval
- Year: 1983
- Time complexity: 𝒪(n)
- Space complexity: requires extra constant space only
Duval's generation
w0 ← First(Σ)
i ← 0
while i ≠ -1 do
for j ← 1 to n-i-1 do
wi+j ← wj-1
output(Prefi(w))
i ← n-1
while i > -1 and wi = Last(Σ) do
i ← i-1
if i > -1 then
wi ← Next(wi)
w0 ← First(Σ)
i ← 0
while i ≠ -1 do
for j ← 1 to n-i-1 do
wi+j ← wj-1
output(Prefi(w))
i ← n-1
while i > -1 and wi = Last(Σ) do
i ← i-1
if i > -1 then
wi ← Next(wi)
Details
- Reference: LYNDEX0002
- Brief description: this algorithm generates all the Lyndon words of length up to n on ordered alphabet Σ, in lexorder
- Author: Jean-Pierre Duval
- Year: 1988
- Time complexity: linear in the size of the output
- Space complexity: 𝒪(n)
