# zbMATH — the first resource for mathematics

A linear-space data structure for range-LCP queries in poly-logarithmic time. (English) Zbl 1441.68021
Wang, Lusheng (ed.) et al., Computing and combinatorics. 24th international conference, COCOON 2018, Qing Dao, China, July 2–4, 2018. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 10976, 615-625 (2018).
Summary: Let $$\mathsf{T}[1,n]$$ be a text of length $$n$$ and $$\mathsf{T}[i,n]$$ be the suffix starting at position $$i$$. Also, for any two strings $$X$$ and $$Y$$, let $$\mathsf{LCP}(X,Y)$$ denote their longest common prefix. The range-LCP of $$\mathsf {T}$$ w.r.t. a range $$[\alpha,\beta]$$, where $$1\leq\alpha<\beta\leq n$$ is ${{{\mathsf{rlcp}}(\alpha,\beta)=\max \{|{\mathsf{LCP}}({\mathsf{T}}[i,n], T[j,n])| \mid i\neq j} \text{ and } {i,j \in [\alpha,\beta]\}}}.$ A. Amir et al. [Lect. Notes Comput. Sci. 7074, 683–692 (2011; Zbl 1350.68298)] introduced the indexing version of this problem, where the task is to build a data structure over $$\mathsf{T}$$, so that $$\mathsf{rlcp}(\alpha,\beta)$$ for any query range $$[\alpha,\beta]$$ can be reported efficiently. They proposed an $$O(n\log^{1+\epsilon}n)$$ space structure with query time $$O(\log\log n)$$, and a linear space (i.e., $$O(n)$$ words) structure with query time $$O(\delta\log\log n)$$, where $$\delta=\beta-\alpha+1$$ is the length of the input range and $$\epsilon > 0$$ is an arbitrarily small constant. Later, M. Patil et al. [Lect. Notes Comput. Sci. 8214, 263–270 (2013; Zbl 1442.68040)] proposed another linear space structure with an improved query time of $$O(\sqrt{\delta}\log^{\epsilon}\delta)$$. This poses an interesting question, whether it is possible to answer $$\mathsf{rlcp}(\cdot,\cdot)$$ queries in poly-logarithmic time using a linear space data structure. In this paper, we settle this question by presenting an $$O(n)$$ space data structure with query time $$O(\log^{1+\epsilon}n)$$ and construction time $$O(n\log n)$$.
For the entire collection see [Zbl 1390.68029].

##### MSC:
 68P05 Data structures 68Q25 Analysis of algorithms and problem complexity 68W32 Algorithms on strings
Full Text: