Longest common extensions in trees

DOI10.1016/J.TCS.2015.08.009MaRDI QIDQ294947zbMATH OpenOpenAlexDBLPWikidataFDO

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

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)

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

Cites work

• scientific article; zbMATH DE number 1617247 (Why is no real title available?)
• scientific article; zbMATH DE number 1670815 (Why is no real title available?)
• scientific article; zbMATH DE number 177536 (Why is no real title available?)
• scientific article; zbMATH DE number 1512678 (Why is no real title available?)
• scientific article; zbMATH DE number 1522932 (Why is no real title available?)
• Algorithms on Strings, Trees and Sequences
• Algorithms – ESA 2004
• Ambivalent Data Structures for Dynamic 2-Edge-Connectivity and k Smallest Spanning Trees
• An O(n log n) algorithm for finding all repetitions in a string
• An \(O(ND)\) difference algorithm and its variations
• Approximate String Matching: A Simpler Faster Algorithm
• Converting SLP to LZ78 in almost Linear Time
• Design and implementation of an efficient priority queue
• Distance oracles beyond the Thorup-Zwick bound
• Fast Algorithms for Finding Nearest Common Ancestors
• Fast parallel and serial approximate string matching
• Fast set intersection and two-patterns matching
• Faster algorithms for string matching with k mismatches
• Finding level-ancestors in trees
• Incremental String Comparison
• Linear time algorithms for finding and representing all the tandem repeats in a string
• Longest common extensions in sublinear space
• Longest common extensions via fingerprinting
• Minimizing diameters of dynamic trees
• Nearest common ancestors: a survey and a new algorithm for a distributed environment
• Space-efficient preprocessing schemes for range minimum queries on static arrays
• Succinct ordinal trees with level-ancestor queries
• The level ancestor problem simplified
• The longest common extension problem revisited and applications to approximate string searching
• The suffix tree of a tree and minimizing sequential transducers
• The tree inclusion problem
• Theoretical and Practical Improvements on the RMQ-Problem, with Applications to LCA and LCE
• Time-space trade-offs for longest common extensions
• Time-space trade-offs for predecessor search

Cited in

(8)

• Efficiently computing runs on a trie
• Longest common extensions in trees
• The longest common extension problem revisited and applications to approximate string searching
• The heaviest induced ancestors problem revisited
• 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)