Tight lower bounds for the longest common extension problem

DOI10.1016/J.IPL.2017.05.003MaRDI QIDQ2628282zbMATH OpenOpenAlexFDO

Authors Dmitry Kosolobov

Publication date 13 June 2017

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1611.02891, http://hdl.handle.net/10138/307544

zbMATH Keywords

data structureslower boundstrade-offcell-probe modellongest common extension

Mathematics Subject Classification ID

Data structures (68P05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Algorithms on strings (68W32)

Abstract: The longest common extension problem is to preprocess a given string of length $n$ into a data structure that uses $S(n)$ bits on top of the input and answers in $T(n)$ time the queries $mathitLCE(i,j)$ computing the length of the longest string that occurs at both positions $i$ and $j$ in the input. We prove that the trade-off $S(n)T(n)=Omega(nlogn)$ holds in the non-uniform cell-probe model provided that the input string is read-only, each letter occupies a separate memory cell, $S(n)=Omega(n)$, and the size of the input alphabet is at least $2^{8lceilS(n)/nceil}$. It is known that this trade-off is tight.

Recommendations

• Longest common extensions in sublinear space
• Time-space trade-offs for longest common extensions
• Time-Space Trade-Offs for Longest Common Extensions
• Small-space LCE data structure with constant-time queries
• The longest common extension problem revisited and applications to approximate string searching

Cites work

• Computing runs on a general alphabet
• Deterministic Sparse Suffix Sorting on Rewritable Texts
• Deterministic sub-linear space LCE data structures with efficient construction
• Fast Algorithms for Finding Nearest Common Ancestors
• Fast lightweight suffix array construction and checking
• Faster longest common extension queries in strings over general alphabets
• Longest common extensions in sublinear space
• On space efficient two dimensional range minimum data structures
• Sparse suffix tree construction in optimal time and space
• Theoretical and Practical Improvements on the RMQ-Problem, with Applications to LCA and LCE
• Time-space trade-offs for longest common extensions

Cited in

(7)

• Practical Performance of Space Efficient Data Structures for Longest Common Extensions.
• Time-Space Trade-Offs for Longest Common Extensions
• Small-space LCE data structure with constant-time queries
• 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
• Tight bounds for the performance of Longest In System on DAGs

This page was built for publication: Tight lower bounds for the longest common extension problem

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