Affiliations: [a] Department of Computer Science, University of Wisconsin - Whitewater, USA. [email protected] | [b] Facebook, Inc., Menlo Park, California, USA. [email protected] | [c] Department of Computer Science, Louisiana State University, USA. [email protected] | [d] Department of Computer Science, University of Central Florida, USA. [email protected]
Correspondence:
[†]
Address for correspondence: Department of Computer Science, University of Central Florida, 117 Harris Center (Building 116), 4000 Central Florida Blvd., Orlando, Florida 32816-2362 USA.
Note: [*] A preliminary version of this work appeared in SPIRE 2013 Conference [13].
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(Sp, Sq)| | i ≤ p < q ≤ j} Here LCP(Sp, Sq) is the longest common prefix of the suffixes of S starting at locations p and q, and |LCP(Sp, Sq)| 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 log1+ɛ 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−ɛ).
Keywords: String Algorithms, Suffix Trees, Range Query
