The Range LCP problem is to preprocess a string $$S[1\dots n]$$, to enable efficient solutions of the following query: given a range [l,i¾źr] as the input, report $$\max _{i, j \in \{l,\ldots ,r\}} |\mathsf {LCP}S_{i}, S_j|$$. Here $$\mathsf {LCP}S_i, S_j$$ is the longest common prefix of the suffixes of S starting at locations i and j and $$|\mathsf {LCP}S_i,S_j|$$ is its length. We study a natural extension of this problem, where the query consists of two ranges. Additionally, we allow a bounded number say $$k\ge 0$$ of mismatches in the $$\mathsf {LCP}$$ computation. Specifically, our task is to report the following when two ranges $$[\ell _1, r_1]$$ and $$[\ell _2,r_2]$$ comes as input: $$\max _{\{\ell _1\le i\le r_1, \ell _2\le j\le r_2\}}|\mathsf {LCP}_kS_i,S_j|$$Here $$\mathsf {LCP}_kS_i,S_j$$ is the longest prefix of $$S_i$$ and $$S_j$$ with at most k mismatches allowed. We show that the queries can be answered in Ok time using an $$On^2/w$$ space data structure, where w is the word size. We also present space efficient data structures for $$k=0$$ and $$k=1$$. For $$k=0$$, we obtain a linear space data structure with query time $$O\sqrt{n/w}\log ^{\epsilon } n$$, where w is the word size and $$\epsilon >0$$ is an arbitrarily small constant.#R##N##R##N#For the case $$k=1$$ we obtain an $$On\log n$$ space data structure with query time $$O\sqrt{n}\log n$$.#R##N##R##N#Finally, we give a reduction from Set Intersection to Range LCP queries, suggesting that it will be very difficult to improve our upper bound by more than a factor of $$O\log ^{\epsilon }n$$.
['Amihood Amir', 'Moshe Lewenstein', 'Sharma V. Thankachan']
Range LCP Queries Revisited