Resumen
We present two modifications of Duval?s algorithm for computing the Lyndon factorization of a string. One of the algorithms has been designed for strings containing runs of the smallest character. It works best for small alphabets and it is able to skip a significant number of characters of the string. Moreover, it can be engineered to have linear time complexity in the worst case. When there is a run-length encoded string R of length ??
?
, the other algorithm computes the Lyndon factorization of R in ??(??)
O
(
?
)
time and in constant space. It is shown by experimental results that the new variations are faster than Duval?s original algorithm in many scenarios.