A Linear Space Data Structure For Range Lcp Queries

Keywords

Range Query; String Algorithms; Suffix Trees

Abstract

Range LCP (longest common prefix) is an extension of the classical LCP problem and is defined as follows: Preprocess a string S[1...n] of n characters, such that whenever an interval [i, j] comes as a query, we can report max{|LCP(S p, S q)| | i ≤ p < q ≤ j} Here LCP(S p, S q) is the longest common prefix of the suffixes of S starting at locations p and q, and |LCP(S p, S q)| is its length. This problem was first addressed by Amir et al. [ISAAC, 2011]. They showed that the query can be answered in O(log log n) time using an O(n log 1+ϵ n) space data structure for an arbitrarily small constant ϵ > 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(dlogd (logn) 1/2-ϵ).

Publication Date

1-1-2018

Publication Title

Fundamenta Informaticae

Volume

163

Issue

3

Number of Pages

245-251

Document Type

Article; Proceedings Paper

Personal Identifier

scopus

DOI Link

https://doi.org/10.3233/FI-2018-1741

Socpus ID

85056316193 (Scopus)

Source API URL

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

This document is currently not available here.

Share

COinS