Prague Stringology Conference 2026

In-Place BWT and Lyndon Array Construction in Constant Space

Abstract:

We show that the BWT and the Lyndon array of a string can be constructed simultaneously using only O(1) additional memory words in the general ordered alphabet model. Our algorithm extends the in-place quadratic-time BWT construction of (Crochemore 2015) by maintaining suffix ranks during the right-to-left construction, from which the Lyndon array is derived via a next-smaller-value procedure. We also consider the construction of the succinct 2n-bit representation of the Lyndon array under the same constant-space constraints. Although not practical, our methods demonstrate that these fundamental structures admit in-place constructions under the strongest possible space bounds, even over unbounded alphabets. We show that the BWT and the Lyndon array of a string can be constructed simultaneously using only O(1) additional memory words in the general ordered alphabet model. Our algorithm extends the in-place quadratic-time BWT construction of {Crochemore 2015) by maintaining suffix ranks during the right-to-left construction, from which the Lyndon array is derived via a next-smaller-value procedure. We also consider the construction of the succinct 2n-bit representation of the Lyndon array under the same constant-space constraints. Although not practical, our methods demonstrate that these fundamental structures admit in-place constructions under the strongest possible space bounds, even over unbounded alphabets.

Download paper:
		PDF	BibTeX reference