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].


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