Conference paper
Algorithms to compute the lyndon array
Prague Stringology Conference (PSC) 2016 (Prague, Czech Republic, 29/08/2016–31/08/2016)
2016
Abstract
We first describe three algorithms for computing the Lyndon array that have been suggested in the literature, but for which no structured exposition has been given. Two of these algorithms execute in quadratic time in the worst case, the third achieves linear time, but at the expense of prior computation of both the suffix array and the inverse suffix array of x. We then go on to describe two variants of a new algorithm that avoids prior computation of global data structures and executes in worst-case n log n time. Experimental evidence suggests that all but one of these five algorithms require only linear execution time in practice, with the two new algorithms faster by a small factor. We conjecture that there exists a fast and worst-case linear-time algorithm to compute the Lyndon array that is also elementary (making no use of global data structures such as the suffix array).
Details
- Title
- Algorithms to compute the lyndon array
- Authors/Creators
- F. Franěk (Author/Creator)A.S.M. Sohidull Islam (Author/Creator)M.S. Rahman (Author/Creator)W.F. Smyth (Author/Creator)
- Conference
- Prague Stringology Conference (PSC) 2016 (Prague, Czech Republic, 29/08/2016–31/08/2016)
- Identifiers
- 991005542503707891
- Murdoch Affiliation
- School of Engineering and Information Technology
- Language
- English
- Resource Type
- Conference paper
Metrics
12 File views/ downloads
79 Record Views