Space efficient construction of Lyndon arrays in linear time

Philip Bille, Jonas Ellert, Johannes Fischer, Inge Li Gørtz, Florian Kurpicz, J. Ian Munro, Eva Rotenberg

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

1 Downloads (Pure)

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 log2 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 Ω(n lg 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 log2 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.

Original languageEnglish
Title of host publicationProceedings of 47th International Colloquium on Automata, Languages and Programming
EditorsArtur Czumaj, Anuj Dawar, Emanuela Merelli
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Publication date1 Jun 2020
Pages14:1--14:18
ISBN (Electronic)9783959771382
DOIs
Publication statusPublished - 1 Jun 2020
Event47th International Colloquium on Automata, Languages, and Programming - Virtual event, Saarbrücken , Germany
Duration: 8 Jul 202011 Jul 2020

Conference

Conference47th International Colloquium on Automata, Languages, and Programming
LocationVirtual event
CountryGermany
CitySaarbrücken
Period08/07/202011/07/2020
SponsorCenter for Perspicuous Computing, Saarland University
SeriesLeibniz International Proceedings in Informatics, LIPIcs
Volume168
ISSN1868-8969

Keywords

  • Lyndon array
  • Lyndon word
  • Nearest smaller suffixes
  • Nearest smaller values
  • String algorithms
  • String suffixes
  • Succinct data structures

Fingerprint Dive into the research topics of 'Space efficient construction of Lyndon arrays in linear time'. Together they form a unique fingerprint.

Cite this