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(nlogn/loglogn) time using asymptotically the same space as T.
Original language | English |
---|---|
Pages (from-to) | 2-9 |
Number of pages | 8 |
Journal | Journal of Discrete Algorithms |
Volume | 50 |
DOIs | |
Publication status | Published - May 2018 |
Externally published | Yes |
Keywords
- Balanced parentheses
- Burrows–Wheeler inversion
- Compressed representation
- Linear time
- Lyndon array