Catalog Home Page

Lyndon Array construction during Burrows-Wheeler inversion

Louza, F.A., Smyth, W.F., Manzini, G. and Telles, G.P. (2018) Lyndon Array construction during Burrows-Wheeler inversion. Journal of Discrete Algorithms, 50 . pp. 2-9.

PDF - Authors' Version
Embargoed until October 2019.

Link to Published Version:
*Subscription may be required


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 bits of space and supports constant time access. This representation can be built in linear time using words of space, or in time using asymptotically the same space as T.

Item Type: Journal Article
Murdoch Affiliation: School of Engineering and Information Technology
Publisher: Elsevier
Copyright: © 2018 Elsevier B.V
Item Control Page Item Control Page