Lyndon Factorization Algorithms for Small Alphabets and Run-Length Encoded Strings
A1 Alkuperäisartikkeli tieteellisessä aikakauslehdessä
ALGORITHMS, Volume 12, issue 6
AbstractWe 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.
Lyndon factorization, string algorithms, run-length encoding
Ghuman , S S , Giaquinta , E & Tarhio , J 2019 , ' Lyndon Factorization Algorithms for Small Alphabets and Run-Length Encoded Strings ' , Algorithms , vol. 12 , no. 6 , 124 . https://doi.org/10.3390/a12060124