Computing minimal and maximal suffixes of a substring

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...

Full description

Saved in:
Bibliographic Details
Published in:Theoretical computer science 2016-07, Vol.638, p.112-121
Main Authors: Babenko, Maxim, Gawrychowski, Paweł, Kociumaka, Tomasz, Kolesnichenko, Ignat, Starikovskaya, Tatiana
Format: Article
Language:English
Subjects:
Computation
Construction
Data structures
Decomposition
Lexicographic order
Maximal suffix
Minimal suffix
Optimization
Preprocessing
Query processing
Substring queries
Texts
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0304-3975
1879-2294
DOI:10.1016/j.tcs.2015.08.023