Longest common extensions in sublinear space

DOI10.1007/978-3-319-19929-0_6MaRDI QIDQ2942246zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Philip Bille, Inge Li Gørtz, Mathias Bæk Tejs Knudsen, Hjalte Wedel Vildhøj, Moshe Lewenstein

Publication date 20 August 2015

Published in Combinatorial Pattern Matching (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Data structures (68P05) Analysis of algorithms and problem complexity (68Q25)

Abstract: The longest common extension problem (LCE problem) is to construct a data structure for an input string $T$ of length $n$ that supports LCE$(i,j)$ queries. Such a query returns the length of the longest common prefix of the suffixes starting at positions $i$ and $j$ in $T$. This classic problem has a well-known solution that uses $O(n)$ space and $O(1)$ query time. In this paper we show that for any trade-off parameter $1leqauleqn$, the problem can be solved in $O(fracnau)$ space and $O(au)$ query time. This significantly improves the previously best known time-space trade-offs, and almost matches the best known time-space product lower bound.

Recommendations

• 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
• Deterministic sub-linear space LCE data structures with efficient construction
• Tight lower bounds for the longest common extension problem

Cites work

• A New Linear-Time ``On-Line Algorithm for Finding the Smallest Initial Palindrome of a String
• An \(O(ND)\) difference algorithm and its variations
• An O(n log n) algorithm for finding all repetitions in a string
• Approximate String Matching: A Simpler Faster Algorithm
• Efficient randomized pattern-matching algorithms
• Fast Algorithms for Finding Nearest Common Ancestors
• Fast parallel and serial approximate string matching
• Faster algorithms for string matching with k mismatches
• Faster sparse suffix sorting
• Incremental String Comparison
• Linear time algorithms for finding and representing all the tandem repeats in a string
• Longest common extensions in sublinear space
• Searching for Gapped Palindromes
• Time-space trade-offs for longest common extensions
• Uniqueness Theorems for Periodic Functions

Cited in

(26)

• Universal compressed text indexing
• Computing the least common subsumer w.r.t. a background terminology
• Time-space trade-offs for longest common extensions
• Tight lower bounds for the longest common extension problem
• Internal shortest absent word queries in constant time and linear space
• Longest common extensions via fingerprinting
• Time-Space Trade-Offs for Longest Common Extensions
• Sublinear space algorithms for the longest common substring problem
• Longest common extensions in trees
• Longest common extensions in sublinear space
• Longest common extensions in trees
• Fully dynamic data structure for LCE queries in compressed space
• Time-space trade-offs for the longest common substring problem
• Longest common extensions with recompression
• Small-space LCE data structure with constant-time queries
• Deterministic sub-linear space LCE data structures with efficient construction
• Faster longest common extension queries in strings over general alphabets
• Practical Performance of Space Efficient Data Structures for Longest Common Extensions.
• String Indexing with Compressed Patterns
• The longest common extension problem revisited and applications to approximate string searching
• On longest common property preserved substring queries
• Online algorithms on antipowers and antiperiods
• Construction of sparse suffix trees and LCE indexes in optimal time and space
• Locally consistent parsing for text indexing in small space
• Longest common extensions with wildcards: trade-off and applications
• Two-dimensional longest common extension queries in compact space

This page was built for publication: Longest common extensions in sublinear space

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