Lyndon Factorization Algorithms for Small Alphabets and Run-Length Encoded Strings
Open Access
- 21 June 2019
- journal article
- research article
- Published by MDPI AG in Algorithms
- Vol. 12 (6) , 124
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 , the other algorithm computes the Lyndon factorization of R in 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.
Keywords
This publication has 7 references indexed in Scilit:
- Faster Lyndon factorization algorithms for SLP and LZ78 compressed textTheoretical Computer Science, 2016
- Improving practical exact string matchingInformation Processing Letters, 2010
- Fast and flexible string matching by combining bit-parallelism and suffix automataACM Journal of Experimental Algorithmics, 2000
- Combinatorics on Words1997
- Fast parallel Lyndon factorization with applicationsTheory of Computing Systems, 1995
- Factorizing words over an ordered alphabetJournal of Algorithms, 1983
- Free Differential Calculus, IV. The Quotient Groups of the Lower Central SeriesAnnals of Mathematics, 1958