Range LCP.(English)Zbl 1350.68298

Asano, Takao (ed.) et al., Algorithms and computation. 22nd international symposium, ISAAC 2011, Yokohama, Japan, December 5–8, 2011. Proceedings. Berlin: Springer (ISBN 978-3-642-25590-8/pbk). Lecture Notes in Computer Science 7074, 683-692 (2011).
Summary: In this paper, we define the Range LCP problem as follows. Preprocess a string $$S$$, of length $$n$$, to enable efficient solutions of the following query:
Given $$[i,j],\;\;0< i \leq j \leq n$$, compute max$$_{\ell , k \in \{i,\cdots ,j\}} \mathrm{LCP}(S _{\ell }, S _{k })$$, where $$\mathrm{LCP}(S _{\ell }, S _{k })$$ is the length of the longest common prefix of the suffixes of $$S$$ starting at locations $$\ell$$ and $$k$$. This is a natural generalization of the classical LCP problem.
Surprisingly, while it is known how to preprocess a string in linear time to enable LCP computation of two suffixes in constant time, this seems quite difficult in the Range LCP problem. It is trivial to answer such queries in time $$O(|j - i|^{2})$$ after a linear-time preprocessing and easy to show an $$O(1)$$ query algorithm after an $$O(|S|^{2})$$ time preprocessing. We provide algorithms that solve the problem with the following complexities:
1. Preprocessing Time: $$O(|S|)$$, Space: $$O(|S|)$$, Query Time: $$O(|j - i|\log \log n)$$.
2. Preprocessing Time: no preprocessing, Space: $$O(|j - i|\log |j - i|)$$, Query Time: $$O(|j - i|\log |j - i|)$$. However, the query just gives the pairs with the longest LCP, not the LCP itself.
3. Preprocessing Time: $$O(|S|\log^{2} |S|)$$, Space: $$O(|S|\log^{1 + \epsilon } |S|)$$ for arbitrary small constant $$\epsilon$$, Query Time: $$O(\log \log |S|)$$.
For the entire collection see [Zbl 1228.68006].

MSC:

 68W32 Algorithms on strings 68W40 Analysis of algorithms
Full Text: