Deterministic sub-linear space LCE data structures with efficient construction

DOI10.4230/LIPICS.CPM.2016.1MaRDI QIDQ5369533zbMATH OpenOpenAlexFDO

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

Publication date 17 October 2017

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

zbMATH Keywords

longest common prefixlongest common extensionsparse suffix array

Mathematics Subject Classification ID

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

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)$.

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

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)