Computing minimal and maximal suffixes of a substring

Maxim Babenko, Pawel Gawrychowski, Tomasz Kociumaka, Ignat Kolesnichenko, Tatiana Starikovskaia

Research output: Contribution to journalSpecial issue (Academic Journal)peer-review

1 Citation (Scopus)
324 Downloads (Pure)

Abstract

We consider the problems of computing the maximal and the minimal non-empty suffixes of substrings of a longer text of length n. For the minimal suffix problem we show that for every τ , 1≤τ≤log⁡n, there exists a linear-space data structure with O(τ) query time and O(nlog⁡n/τ) preprocessing time. As a sample application, we show that this data structure can be used to compute the Lyndon decomposition of any substring of the text in O(kτ) time, where k is the number of distinct factors in the decomposition. For the maximal suffix problem, we give a linear-space structure with O(1) query time and O(n) preprocessing time. In other words, we simultaneously achieve both the optimal query time and the optimal construction time.
Original languageEnglish
Pages (from-to)112-121
Number of pages10
JournalTheoretical Computer Science
Volume638
Early online date28 Aug 2015
DOIs
Publication statusPublished - 25 Jul 2016

Keywords

  • Data structures
  • Substring queries
  • Lexicographic order
  • Minimal suffix
  • Maximal suffix

Fingerprint Dive into the research topics of 'Computing minimal and maximal suffixes of a substring'. Together they form a unique fingerprint.

Cite this