zbMATH — the first resource for mathematics

A linear space data structure for range LCP queries. (English) Zbl 1405.68463
Summary: Range LCP (longest common prefix) is an extension of the classical LCP problem and is defined as follows: Preprocess a string $$S [1\dots n]$$ of $$n$$ characters, such that whenever an interval $$[i,j]$$ comes as a query, we can report $$\max\{|\mathrm{LCP}(S_p , S_q )|\mid i \leq p < q \leq j \}$$. Here $$\mathrm{LCP}(S_p , S_q)$$ is the longest common prefix of the suffixes of $$S$$ starting at locations $$p$$ and $$q$$, and $$|\mathrm{LCP}(S_p , S_q )|$$ is its length. This problem was first addressed by [A. Amir et al., Lect. Notes Comput. Sci. 7074, 683–692 (2011; Zbl 1350.68298)]. They showed that the query can be answered in $$O (\log \log n )$$ time using an $$O (n \log^{1+\epsilon} n )$$ space data structure for an arbitrarily small constant $$\epsilon > 0$$. In an attempt to reduce the space bound, they presented a linear space data structure of $$O (d \log \log n)$$ query time, where $$d = (j - i + 1)$$. In this paper, we present a new linear space data structure with an improved query time of $$O\left( \frac{\sqrt{ d \log d}}{(\log n)^{1/2 -\epsilon}}\right)$$.

MSC:
 68W32 Algorithms on strings 68P05 Data structures
Full Text: