Time-Space Trade-Offs for Longest Common Extensions

DOI10.1007/978-3-642-31265-6_24MaRDI QIDQ2904502zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Philip Bille, Inge Li Gørtz, Benjamin Sach, Hjalte Wedel Vildhøj

Publication date 14 August 2012

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

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

Mathematics Subject Classification ID

Data structures (68P05) Analysis of algorithms and problem complexity (68Q25) Algorithms on strings (68W32)

Abstract: We revisit the longest common extension (LCE) problem, that is, preprocess a string $T$ into a compact data structure that supports fast LCE queries. An LCE query takes a pair $(i,j)$ of indices in $T$ and returns the length of the longest common prefix of the suffixes of $T$ starting at positions $i$ and $j$. We study the time-space trade-offs for the problem, that is, the space used for the data structure vs. the worst-case time for answering an LCE query. Let $n$ be the length of $T$. Given a parameter $au$, $1leqauleqn$, we show how to achieve either $O(infracnsqrtau)$ space and $O(au)$ query time, or $O(infracnau)$ space and $O(aulog(|LCE(i,j)|/au))$ query time, where $|LCE(i,j)|$ denotes the length of the LCE returned by the query. These bounds provide the first smooth trade-offs for the LCE problem and almost match the previously known bounds at the extremes when $au=1$ or $au=n$. We apply the result to obtain improved bounds for several applications where the LCE problem is the computational bottleneck, including approximate string matching and computing palindromes. We also present an efficient technique to reduce LCE queries on two strings to one string. Finally, we give a lower bound on the time-space product for LCE data structures in the non-uniform cell probe model showing that our second trade-off is nearly optimal.

Recommendations

• Time-space trade-offs for longest common extensions
• Practical Performance of Space Efficient Data Structures for Longest Common Extensions.
• Time-space trade-offs for the longest common substring problem
• Space-Time Tradeoffs for Longest-Common-Prefix Array Computation
• Longest common extensions in sublinear space
• Tight lower bounds for the longest common extension problem
• The longest common extension problem revisited and applications to approximate string searching
• Faster longest common extension queries in strings over general alphabets
• Linear time algorithms for generalizations of the longest common substring problem

Cites work

• A New Linear-Time ``On-Line Algorithm for Finding the Smallest Initial Palindrome of a String
• Algorithms on Strings, Trees and Sequences
• 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 algorithms to compute compressed longest common substrings and compressed palindromes
• Efficient randomized pattern-matching algorithms
• Efficient string matching
• Fast Algorithms for Finding Nearest Common Ancestors
• Fast parallel and serial approximate string matching
• Faster algorithms for string matching with k mismatches
• Finding all periods and initial palindromes of a string in parallel
• scientific article; zbMATH DE number 177800 (Why is no real title available?)
• Incremental String Comparison
• Linear time algorithms for finding and representing all the tandem repeats in a string
• Linear work suffix array construction
• Palindrome complexity.
• Quorums from difference covers
• Searching for Gapped Palindromes
• Space efficient search for maximal repetitions
• Space-Time Tradeoffs for Longest-Common-Prefix Array Computation
• The derivation of on-line algorithms, with an application to finding palindromes
• The longest common extension problem revisited and applications to approximate string searching
• Theoretical and Practical Improvements on the RMQ-Problem, with Applications to LCA and LCE
• Uniform deterministic dictionaries

Cited in

(14)

• Time-space trade-offs for Lempel-Ziv compressed indexing
• Time-space trade-offs for longest common extensions
• Tight lower bounds for the longest common extension problem
• Longest common extensions via fingerprinting
• Sublinear space algorithms for the longest common substring problem
• Longest common extensions in trees
• Longest common extensions in sublinear space
• Space-Time Tradeoffs for Longest-Common-Prefix Array Computation
• Time-space trade-offs for the longest common substring problem
• Improved space-time tradeoffs for approximate full-text indexing with one edit error
• Small-space LCE data structure with constant-time queries
• Deterministic sub-linear space LCE data structures with efficient construction
• Practical Performance of Space Efficient Data Structures for Longest Common Extensions.
• The longest common extension problem revisited and applications to approximate string searching

This page was built for publication: Time-Space Trade-Offs for Longest Common Extensions

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