Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
433741 | Theoretical Computer Science | 2016 | 10 Pages |
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≤τ≤logn1≤τ≤logn, there exists a linear-space data structure with O(τ)O(τ) query time and O(nlogn/τ)O(nlogn/τ) 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τ)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)O(1) query time and O(n)O(n) preprocessing time. In other words, we simultaneously achieve both the optimal query time and the optimal construction time.