A linear-space data structure for range-LCP queries in poly-logarithmic time (Q5918832): Difference between revisions

In this paper, the authors study the range-LCP problem (or rlcp), which asks, given a text \(T\) of length \(n\), for the Longest Common Prefix (LCP) of suffixes of \(T\) (namely \(T[i,n]\) and \(T[j,n]\)) among all \(\alpha\leq i\neq j\leq \beta\), where \(\alpha\) and \(\beta\) are integers (satisfying \(1\leq \alpha<\beta\leq n\)) given as input. The main question raised and positively answered by the authors is whether it is possible to answer rlcp in polylogarithmic time, using a linear-space data structure. More precisely, the data structure used takes \(O(n)\) space and is constructed in \(O(n\log n)\) time. Using the above-mentioned data structure, rlcp can then be answered in \(O(\log^{1+\varepsilon} n)\) time, for any \(\varepsilon>0\). Papers dealing with string algorithms are not always easy to follow for the non-specialist, as this topic has a long and rich history, uses many notations, and (as is the case here) aims at improving time/space complexities and thus provides detailed and thorough analyses. This paper is no exception. One has to be familiar with string algorithms (and in particular with suffix arrays, suffix trees and of course LCP issues) to understand the paper's contents.