Time-Space Trade-Offs for Longest Common Extensions

DOI10.1007/978-3-642-31265-6_24zbMath1358.68332DBLPconf/cpm/BilleGSV12arXiv1211.0270OpenAlexW2260066933WikidataQ60554436 ScholiaQ60554436MaRDI QIDQ2904502

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

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

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

Related Items (4)

Fingerprints in compressed strings ⋮ Time-space trade-offs for Lempel-Ziv compressed indexing ⋮ Time-space trade-offs for longest common extensions ⋮ Improved space-time tradeoffs for approximate full-text indexing with one edit error

Cites Work

• Unnamed Item
• Quorums from difference covers
• Space efficient search for maximal repetitions
• The longest common extension problem revisited and applications to approximate string searching
• Efficient algorithms to compute compressed longest common substrings and compressed palindromes
• An \(O(ND)\) difference algorithm and its variations
• The derivation of on-line algorithms, with an application to finding palindromes
• Linear time algorithms for finding and representing all the tandem repeats in a string
• Palindrome complexity.
• Finding all periods and initial palindromes of a string in parallel
• Approximate String Matching: A Simpler Faster Algorithm
• Fast Algorithms for Finding Nearest Common Ancestors
• An O(n log n) algorithm for finding all repetitions in a string
• Linear work suffix array construction
• Searching for Gapped Palindromes
• Space-Time Tradeoffs for Longest-Common-Prefix Array Computation
• Efficient randomized pattern-matching algorithms
• Efficient string matching
• A New Linear-Time ``On-Line Algorithm for Finding the Smallest Initial Palindrome of a String
• Fast parallel and serial approximate string matching
• Algorithms on Strings, Trees and Sequences
• Incremental String Comparison
• Faster algorithms for string matching with k mismatches
• Uniform deterministic dictionaries
• Theoretical and Practical Improvements on the RMQ-Problem, with Applications to LCA and LCE

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