Two-dimensional longest common extension queries in compact space

DOI10.4230/LIPICS.STACS.2025.38MaRDI QIDQ7287774zbMATH OpenFDO

Authors Arnab Ganguly, Daniel Gibney, Rahul Shah, Sharma V. Thankachan

Publication date 24 June 2026

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.STACS.2025.38

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

• A Generalization of the Suffix Tree to Square Matrices, with Applications
• Collapsing the hierarchy of compressed data structures: suffix arrays in optimal compressed space
• Compact text indexing for advanced pattern matching problems: parameterized, order-isomorphic, 2D, etc. (invited talk)
• Compressed Suffix Arrays and Suffix Trees with Applications to Text Indexing and String Matching
• Compressibility measures for two-dimensional data
• Fast lightweight suffix array construction and checking
• Faster longest common extension queries in strings over general alphabets
• Fully dynamic data structure for LCE queries in compressed space
• Fully functional parameterized suffix trees in compact space
• Fully functional suffix trees and optimal text searching in BWT-runs bounded space
• Generalizations of suffix arrays to multi-dimensional matrices.
• scientific article; zbMATH DE number 2119665 (Why is no real title available?)
• scientific article; zbMATH DE number 7788633 (Why is no real title available?)
• LF successor: compact space indexing for order-isomorphic pattern matching
• Linear-time construction of two-dimensional suffix trees
• Longest common extensions in sublinear space
• Near-optimal search time in -optimal space, and vice versa
• Opportunistic data structures with applications
• Optimal suffix tree construction with large alphabets
• Optimal-Time Dictionary-Compressed Indexes
• pBWT: achieving succinct data structures for parameterized pattern matching and related problems
• Quorums from difference covers
• String synchronizing sets: sublinear-time BWT construction and optimal LCE data structure
• Sublinear algorithms for approximating string compressibility
• Succinct indexable dictionaries with applications to encoding \(k\)-ary trees, prefix sums and multisets
• Time-space trade-offs for longest common extensions
• Toward a Definitive Compressibility Measure for Repetitive Sequences

This page was built for publication: Two-dimensional longest common extension queries in compact space

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