부산대학교 도서관

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))j 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 ¹+ε 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(d log d/(log n)¹=²-ε). [ABSTRACT FROM AUTHOR]