Space Efficient Construction of Lyndon Arrays in Linear Time

Abstract

Given a string $S$ of length $n$, its Lyndon array identifies for each suffix $S[i..n]$ the next lexicographically smaller suffix $S[j..n]$, i.e. the minimal index $j > i$ with $S[i..n] ≻ S[j..n]$. Apart from its plain $(n \log_2 n)$-bit array representation, the Lyndon array can also be encoded as a succinct parentheses sequence that requires only $2n$ bits of space. While linear time construction algorithms for both representations exist, it has previously been unknown if the same time bound can be achieved with less than $\Omega(n \log n)$ bits of additional working space. We show that, in fact, $o(n)$ additional bits are sufficient to compute the succinct $2n$-bit version of the Lyndon array in linear time. For the plain $(n \log_2 n)$-bit version, we only need $O(1)$ additional words to achieve linear time. Our space efficient construction algorithm makes the Lyndon array more accessible as a fundamental data structure in applications like full-text indexing.

BibTeX

@inproceedings{Kurpicz2020ICALP,
  author    = {Philip Bille and Jonas Ellert and Johannes Fischer and Inge Li Gørtz and Florian Kurpicz and J. Ian Munro and Eva Rotenberg},
  title     = {Space Efficient Construction of Lyndon Arrays in Linear Time},
  booktitle = {ICALP},
  series    = {LIPIcs},
  volume    = {168},
  pages     = {14:1–14:18},
  publisher = {Springer},
  doi       = {10.4230/LIPIcs.ICALP.2020.14},
  year      = {2020}
}

PDF