Tight lower bounds for the longest common extension problem

DOI10.1016/j.ipl.2017.05.003zbMath1409.68355arXiv1611.02891OpenAlexW2575324250MaRDI QIDQ2628282

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

zbMATH Keywords

data structureslower boundstrade-offcell-probe modellongest common extension

Mathematics Subject Classification ID

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

Related Items (3)

Internal shortest absent word queries in constant time and linear space ⋮ Practical Performance of Space Efficient Data Structures for Longest Common Extensions. ⋮ Small-space LCE data structure with constant-time queries

Cites Work

• Computing runs on a general alphabet
• Time-space trade-offs for longest common extensions
• Deterministic Sparse Suffix Sorting on Rewritable Texts
• Longest Common Extensions in Sublinear Space
• Fast Algorithms for Finding Nearest Common Ancestors
• 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
• Theoretical and Practical Improvements on the RMQ-Problem, with Applications to LCA and LCE
• Deterministic Sub-Linear Space LCE Data Structures With Efficient Construction
• Faster Longest Common Extension Queries in Strings over General Alphabets

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