Lyndon Array Construction during Burrows-Wheeler Inversion

Felipe A. Louza, W. F. Smyth, Giovanni Manzini +1

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 algorit…