Longest common extensions in trees

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

zbMATH Keywords

longest common prefixpattern matching in treessuffix tree of a tree

Mathematics Subject Classification ID

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