Abstrakti
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 rho, the other algorithm computes the Lyndon factorization of R in O (rho) 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.
Alkuperäiskieli | Englanti |
---|---|
Artikkeli | 124 |
Sivumäärä | 11 |
Julkaisu | ALGORITHMS |
Vuosikerta | 12 |
Numero | 6 |
DOI - pysyväislinkit | |
Tila | Julkaistu - kesäk. 2019 |
OKM-julkaisutyyppi | A1 Julkaistu artikkeli, soviteltu |