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

Abstract

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).

Publication Date

1-1-2018

Publication Title

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

Volume

10976 LNCS

Number of Pages

615-625

Document Type

Article; Proceedings Paper

Personal Identifier

scopus

DOI Link

https://doi.org/10.1007/978-3-319-94776-1_51

Socpus ID

85049697580 (Scopus)

Source API URL

https://api.elsevier.com/content/abstract/scopus_id/85049697580

This document is currently not available here.

Share

COinS