In-Place BWT and Lyndon Array Construction in Constant Space
By: Felipe A. Louza, Arnaud Lefebvre
We present an extension of the in-place BWT algorithm of Crochemore et al. [8] that enables the construction of the Lyndon array using O(1) extra space. Our approach incrementally maintains the lexicographic ranks of the suffixes during the right-to-left BWT construction and then derives the Lyndon array through a simple next-smaller-value procedure. Although not intended for practical use due to its quadratic running time, the method is conceptually simple and works for unbounded alphabets.
Similar Papers
Fast and memory-efficient BWT construction of repetitive texts using Lyndon grammars
Data Structures and Algorithms
Finds patterns in huge data faster.
Merging RLBWTs adaptively
Data Structures and Algorithms
Merges compressed text data much faster.
Merging RLBWTs adaptively
Data Structures and Algorithms
Combines two compressed lists to make one faster.