Abstract
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.
Original language | English |
---|---|
Article number | 124 |
Number of pages | 11 |
Journal | Algorithms |
Volume | 12 |
Issue number | 6 |
DOIs | |
Publication status | Published - Jun 2019 |
MoE publication type | A1 Journal article-refereed |
Keywords
- Lyndon factorization
- string algorithms
- run-length encoding