Florian Kurpicz
Paper Accepted at ICALP 2020

Space Efficient Construction of Lyndon Arrays in Linear Time

Our paper "Space Efficient Construction of Lyndon Arrays in Linear Time" has been accepted at ICALP 2020. You can find the paper here (DOI).

Abstract

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 variant of this algorithm computes the plain (n lg(n)-bit) version of the Lyndon array using only O(1) words of additional working space. All previous algorithms are either not linear, or use at least nlgn bits of additional working space. Also in practice, our new algorithms outperform the previous best ones by an order of magnitude, both in terms of time and space.