Longest common extensions in trees

DOI10.1016/J.TCS.2015.08.009zbMATH Open1345.68115DBLPjournals/tcs/BilleGGLW16OpenAlexW2166482260WikidataQ60554352 ScholiaQ60554352MaRDI QIDQ294947FDOQ294947

Authors: Philip Bille, Paweł Gawrychowski, Inge Li Gørtz, Gad M. Landau, Oren Weimann 

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

Recommendations

• Longest common extensions in trees
• Longest common extension
• scientific article; zbMATH DE number 4145922
• Lowest common ancestors in trees and directed acyclic graphs
• Longest common extensions with recompression
• scientific article; zbMATH DE number 1439439
• Finding largest common embeddable subtrees
• On finding common subtrees
• scientific article; zbMATH DE number 719398
• Longest common extensions via fingerprinting

zbMATH Keywords

longest common prefixpattern matching in treessuffix tree of a tree

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Data structures (68P05) Database theory (68P15)

Cites Work

• Algorithms on Strings, Trees and Sequences
• Succinct ordinal trees with level-ancestor queries
• Title not available (Why is that?)
• The level ancestor problem simplified
• Time-space trade-offs for predecessor search
• Space-efficient preprocessing schemes for range minimum queries on static arrays
• Fast set intersection and two-patterns matching
• Ambivalent Data Structures for Dynamic 2-Edge-Connectivity and k Smallest Spanning Trees
• Distance oracles beyond the Thorup-Zwick bound
• 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
• Title not available (Why is that?)
• Title not available (Why is that?)
• Longest common extensions via fingerprinting
• Longest common extensions in sublinear space
• 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
• Title not available (Why is that?)
• Design and implementation of an efficient priority queue
• Fast parallel and serial approximate string matching
• Incremental String Comparison
• Title not available (Why is that?)
• 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
• Algorithms – ESA 2004
• 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

Cited In (8)

• Efficiently computing runs on a trie
• Longest common extensions in trees
• The heaviest induced ancestors problem revisited
• The longest common extension problem revisited and applications to approximate string searching
• Minimal unique palindromic substrings after single-character substitution
• The common prefix problem on trees
• Longest common extensions with recompression
• Computing runs on a trie

This page was built for publication: Longest common extensions in trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q294947)