Lyndon Factorization Algorithms for Small Alphabets and Run-Length Encoded Strings

Sukhpal Singh Ghuman, Emanuele Giaquinta, Jorma Tarhio*

*Tämän työn vastaava kirjoittaja

Tutkimustuotos: LehtiartikkeliArticleScientificvertaisarvioitu

59 Lataukset (Pure)

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äiskieliEnglanti
Artikkeli124
Sivumäärä11
JulkaisuALGORITHMS
Vuosikerta12
Numero6
DOI - pysyväislinkit
TilaJulkaistu - kesäkuuta 2019
OKM-julkaisutyyppiA1 Julkaistu artikkeli, soviteltu

Siteeraa tätä