Time-space trade-offs for longest common extensions

DOI10.1016/j.jda.2013.06.003zbMath1284.68208DBLPjournals/jda/BilleGSV14OpenAlexW2040972922WikidataQ60554404 ScholiaQ60554404MaRDI QIDQ2442815

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

Publication date: 1 April 2014

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jda.2013.06.003

zbMATH Keywords

approximate string matchingpalindromelongest common extensiontime-space trade-offtandem repeat

Mathematics Subject Classification ID

Combinatorics on words (68R15) Data structures (68P05) Algorithms on strings (68W32)

Related Items (7)

Longest common extensions in trees ⋮ Tight lower bounds for the longest common extension problem ⋮ Longest Common Extensions in Sublinear Space ⋮ Longest common substring with approximately \(k\) mismatches ⋮ Internal shortest absent word queries in constant time and linear space ⋮ Practical Performance of Space Efficient Data Structures for Longest Common Extensions. ⋮ Small-space LCE data structure with constant-time queries

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
• On space efficient two dimensional range minimum data structures
• 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
• Time-Space Trade-Offs for Longest Common Extensions
• 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