Longest common extensions in trees
From MaRDI portal
Publication:294947
DOI10.1016/j.tcs.2015.08.009zbMath1345.68115OpenAlexW2166482260WikidataQ60554352 ScholiaQ60554352MaRDI QIDQ294947
Paweł Gawrychowski, Gad M. Landau, Oren Weimann, Inge Li Gørtz, Philip Bille
Publication date: 16 June 2016
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2015.08.009
Analysis of algorithms and problem complexity (68Q25) Database theory (68P15) Data structures (68P05)
Related Items (3)
Efficiently computing runs on a trie ⋮ Minimal unique palindromic substrings after single-character substitution ⋮ Computing runs on a trie
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The level ancestor problem simplified
- The longest common extension problem revisited and applications to approximate string searching
- Nearest common ancestors: a survey and a new algorithm for a distributed environment
- Fast set intersection and two-patterns matching
- An \(O(ND)\) difference algorithm and its variations
- The suffix tree of a tree and minimizing sequential transducers
- Finding level-ancestors in trees
- 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 via Fingerprinting
- Time-space trade-offs for predecessor search
- Longest Common Extensions in Sublinear Space
- Succinct ordinal trees with level-ancestor queries
- Space-Efficient Preprocessing Schemes for Range Minimum Queries on Static Arrays
- Approximate String Matching: A Simpler Faster Algorithm
- The tree inclusion problem
- Fast Algorithms for Finding Nearest Common Ancestors
- An O(n log n) algorithm for finding all repetitions in a string
- Design and implementation of an efficient priority queue
- Fast parallel and serial approximate string matching
- Algorithms on Strings, Trees and Sequences
- Ambivalent Data Structures for Dynamic 2-Edge-Connectivity and k Smallest Spanning Trees
- Incremental String Comparison
- Minimizing diameters of dynamic trees
- Faster algorithms for string matching with k mismatches
- Converting SLP to LZ78 in almost Linear Time
- Theoretical and Practical Improvements on the RMQ-Problem, with Applications to LCA and LCE
- Distance Oracles beyond the Thorup--Zwick Bound
- Algorithms – ESA 2004
This page was built for publication: Longest common extensions in trees
