A Linear-Space Data Structure For Range-Lcp Queries In Poly-Logarithmic Time

Let (Formula Presented) be a text of length n and (Formula Presented) be the suffix starting at position i. Also, for any two strings X and Y, let (Formula Presented) denote their longest common prefix. The range-LCP of (Formula Presented) w.r.t. a range (Formula Presented), where (Formula Presented) is Amir et al. [ISAAC 2011] introduced the indexing version of this problem, where the task is to build a data structure over (Formula Presented), so that (Formula Presented) for any query range (Formula Presented) can be reported efficiently. They proposed an (Formula Presented) space structure with query time (Formula Presented), and a linear space (i.e., O(n) words) structure with query time (Formula Presented), where (Formula Presented) is the length of the input range and (Formula Presented) is an arbitrarily small constant. Later, Patil et al. [SPIRE 2013] proposed another linear space structure with an improved query time of (Formula Presented). This poses an interesting question, whether it is possible to answer (Formula Presented) queries in poly-logarithmic time using a linear space data structure. In this paper, we settle this question by presenting an O(n) space data structure with query time (Formula Presented) and construction time (Formula Presented)