Longest Common Extensions in Sublinear Space
From MaRDI portal
Publication:2942246
DOI10.1007/978-3-319-19929-0_6zbMath1380.68139DBLPconf/cpm/BilleGKLV15arXiv1504.02671OpenAlexW1958452835WikidataQ60554369 ScholiaQ60554369MaRDI QIDQ2942246
Philip Bille, Mathias Bæk Tejs Knudsen, Hjalte Wedel Vildhøj, Inge Li Gørtz, 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
Related Items (8)
Longest common extensions in trees ⋮ Tight lower bounds for the longest common extension problem ⋮ Longest Common Extensions in Sublinear Space ⋮ Internal shortest absent word queries in constant time and linear space ⋮ String Indexing with Compressed Patterns ⋮ Universal compressed text indexing ⋮ Practical Performance of Space Efficient Data Structures for Longest Common Extensions. ⋮ Small-space LCE data structure with constant-time queries
Cites Work
- An \(O(ND)\) difference algorithm and its variations
- Linear time algorithms for finding and representing all the tandem repeats in a string
- Time-space trade-offs for longest common extensions
- Longest Common Extensions in Sublinear Space
- Faster Sparse Suffix Sorting
- 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
- Searching for Gapped Palindromes
- Efficient randomized pattern-matching algorithms
- A New Linear-Time ``On-Line Algorithm for Finding the Smallest Initial Palindrome of a String
- Fast parallel and serial approximate string matching
- Incremental String Comparison
- Faster algorithms for string matching with k mismatches
- Uniqueness Theorems for Periodic Functions
This page was built for publication: Longest Common Extensions in Sublinear Space
