×

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

Citations:

Zbl 1350.68298
Full Text: DOI