A linear-space data structure for range-LCP queries in poly-logarithmic time (Q5918832)
From MaRDI portal
scientific article; zbMATH DE number 7203021
Language | Label | Description | Also known as |
---|---|---|---|
English | A linear-space data structure for range-LCP queries in poly-logarithmic time |
scientific article; zbMATH DE number 7203021 |
Statements
A linear-space data structure for range-LCP queries in poly-logarithmic time (English)
0 references
23 May 2020
0 references
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.
0 references
string algorithms
0 references
longest common prefix
0 references
indexing version
0 references