Tight lower bounds for the longest common extension problem

DOI10.1016/J.IPL.2017.05.003zbMATH Open1409.68355arXiv1611.02891OpenAlexW2575324250MaRDI QIDQ2628282FDOQ2628282

Authors: Dmitry Kosolobov 

Publication date: 13 June 2017

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

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.

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

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

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)

Cites Work

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

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)