Space Efficient Construction of Lyndon Arrays in Linear Time

Philip Bille, Jonas Ellert, Johannes Fischer +4

We present the first linear time algorithm to construct the $2n$-bit version of the Lyndon array for a string of length $n$ using only $o(n)$ bits of working space. A simpler varia…