In-Place BWT and Lyndon Array Construction in Constant Space

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…