Find in Library

We present two modifications of Duval&#8217;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 <i>R</i> of length <inline-formula> <math display="inline"> <semantics> <mi>&#961;</mi> </semantics> </math> </inline-formula>, the other algorithm computes the Lyndon factorization of <i>R</i> in <inline-formula> <math display="inline"> <semantics> <mrow> <mi>O</mi> <mo>(</mo> <mi>&#961;</mi> <mo>)</mo> </mrow> </semantics> </math> </inline-formula> time and in constant space. It is shown by experimental results that the new variations are faster than Duval&#8217;s original algorithm in many scenarios.