Paper Info
Title
Lyndon Array Construction during Burrows-Wheeler Inversion.
Abstract
In this paper we present an algorithm to compute the Lyndon array of a string T of length n as a byproduct of the inversion of the Burrows–Wheeler transform of T. Our algorithm runs in linear time using only a stack in addition to the data structures used for Burrows–Wheeler inversion. We compare our algorithm with two other linear-time algorithms for Lyndon array construction and show that computing the Burrows–Wheeler transform and then constructing the Lyndon array is competitive compared to the known approaches. We also propose a new balanced parenthesis representation for the Lyndon array that uses 2n+o(n) bits of space and supports constant time access. This representation can be built in linear time using O(n) words of space, or in O(nlog⁡n/log⁡log⁡n) time using asymptotically the same space as T.
Year
DOI
Venue
2018
10.1016/j.jda.2018.08.001
Journal of Discrete Algorithms
Keywords
DocType
Volume
Lyndon array,Burrows–Wheeler inversion,Linear time,Compressed representation,Balanced parentheses
Journal
50
ISSN
Citations 
PageRank 
1570-8667
0
0.34
References 
Authors
10
4
Name
Order
Citations
PageRank
Felipe Alves da Louza1409.13
W. F. Smyth273068.91
Giovanni Manzini31584111.42
Guilherme P. Telles419524.72