Small-space LCE data structure with constant-time queries

DOI10.4230/LIPIcs.MFCS.2017.10zbMath1441.68026arXiv1702.07458OpenAlexW2773679974MaRDI QIDQ5111224

Hideo Bannai, Takaaki Nishimoto, Yuka Tanimura, Shunsuke Inenaga, Masayuki Takeda

Publication date: 26 May 2020

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

zbMATH Keywords

longest common extension\(t\)-coverstruncated suffix trees

Mathematics Subject Classification ID

Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Data structures (68P05)

Related Items (3)

Internal shortest absent word queries in constant time and linear space ⋮ Unnamed Item ⋮ A compressed dynamic self-index for highly repetitive text collections

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The level ancestor problem simplified
• Searching for gapped palindromes
• Efficient string matching with k mismatches
• Surpassing the information theoretic bound with fusion trees
• Finding level-ancestors in trees
• Application of Lempel-Ziv factorization to the approximation of grammar-based compression.
• Truncated suffix trees and their application to data compression.
• Linear time algorithms for finding and representing all the tandem repeats in a string
• Space-efficient representation of truncated suffix trees, with applications to Markov order estimation
• Fingerprints in compressed strings
• Time-space trade-offs for longest common extensions
• Tight lower bounds for the longest common extension problem
• Optimal Bounds for Computing $$\alpha $$ α -gapped Repeats
• Construction of a de Bruijn Graph for Assembly from a Truncated Suffix Tree
• Longest Common Extensions in Sublinear Space
• Computing Longest Single-arm-gapped Palindromes in a String
• Suffix Arrays: A New Method for On-Line String Searches
• Fast Algorithms for Finding Nearest Common Ancestors
• Approximating LZ77 via Small-Space Multiple-Pattern Matching
• Linear work suffix array construction
• Fast Lightweight Suffix Array Construction and Checking
• Space-Time Tradeoffs for Longest-Common-Prefix Array Computation
• A universal algorithm for sequential data compression
• Algorithms on Strings, Trees and Sequences
• Incremental String Comparison
• Efficiently Finding All Maximal alpha-gapped Repeats
• Fully Dynamic Data Structure for LCE Queries in Compressed Space
• Finger Search in Grammar-Compressed Strings
• Longest Common Extensions with Recompression.
• A new characterization of maximal repetitions by Lyndon trees
• 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: Small-space LCE data structure with constant-time queries