A Linear Space Data Structure for Range LCP Queries*
Arnab Ganguly, Manish M. Patil, Rahul Shah, Sharma V. Thankachan · Fundamenta Informaticae · 2018
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 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−ɛ).