Duval's Factorization
Input:
w[1..n] a word of length n
Output:
The Duval's factorization of w in Lyndon words


T
r
y

i
t


w

Fact←∅
k←0
while k < n do
i←k+1
j←k+2
while j < n+1 and w[i] ≤ w[j] do
if w[i] < w[j] then
i←k+1
j←j+1
else
i←i+1
j←j+1
repeat
k←k+(j-i)
Fact←Fact ∪ {k}
until i≤k
return Fact
Reference
J.-P. Duval
Factorizing words over an ordered alphabet
Journal of Algorithms, Volume 4, Issue 4, December 1983, Pages 363-381

Valid XHTML 1.0 Strict CSS Valide !