Murdoch University Research Repository

Welcome to the Murdoch University Research Repository

The Murdoch University Research Repository is an open access digital collection of research
created by Murdoch University staff, researchers and postgraduate students.

Learn more

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
Download (389kB) | Preview
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


Downloads per month over past year