Deterministic sub-linear space LCE data structures with efficient construction

DOI10.4230/LIPICS.CPM.2016.1zbMATH Open1380.68161arXiv1601.07670OpenAlexW2963987971MaRDI QIDQ5369533FDOQ5369533

Authors: Yuka Tanimura, Hideo Bannai, Shunsuke Inenaga, Simon J. Puglisi, Masayuki Takeda, Tomohiro I 

Publication date: 17 October 2017

Abstract: Given a string $S$ of $n$ symbols, a longest common extension query $mathsfLCE(i,j)$ asks for the length of the longest common prefix of the $i$th and $j$th suffixes of $S$. LCE queries have several important applications in string processing, perhaps most notably to suffix sorting. Recently, Bille et al. (J. Discrete Algorithms 25:42-50, 2014, Proc. CPM 2015: 65-76) described several data structures for answering LCE queries that offers a space-time trade-off between data structure size and query time. In particular, for a parameter $1leqauleqn$, their best deterministic solution is a data structure of size $O(n/au)$ which allows LCE queries to be answered in $O(au)$ time. However, the construction time for all deterministic versions of their data structure is quadratic in $n$. In this paper, we propose a deterministic solution that achieves a similar space-time trade-off of $O(auminlogau,logfracnau)$ query time using $O(n/au)$ space, but significantly improve the construction time to $O(nau)$.

Full work available at URL: https://arxiv.org/abs/1601.07670

Recommendations

• Longest common extensions in sublinear space
• Small-space LCE data structure with constant-time queries
• Time-space trade-offs for longest common extensions
• Time-Space Trade-Offs for Longest Common Extensions
• Fully dynamic data structure for LCE queries in compressed space

zbMATH Keywords

longest common prefixlongest common extensionsparse suffix array

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Data structures (68P05)

Cited In (7)

• Practical Performance of Space Efficient Data Structures for Longest Common Extensions.
• Tight lower bounds for the longest common extension problem
• Small-space LCE data structure with constant-time queries
• Fully dynamic data structure for LCE queries in compressed space
• Longest common extensions in sublinear space
• Internal shortest absent word queries in constant time and linear space
• Time-space trade-offs for longest common extensions

This page was built for publication: Deterministic sub-linear space LCE data structures with efficient construction

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5369533)