Generalized LCS

DOI10.1016/j.tcs.2008.08.037zbMath1155.68021OpenAlexW2912710002MaRDI QIDQ2378524

Amihood Amir, Tzvika Hartman, B. Riva Shalom, Oren Kapah, Dekel Tsur

Publication date: 8 January 2009

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2008.08.037

zbMATH Keywords

matricestreeslongest common subsequencenon crossing matching

Mathematics Subject Classification ID

Searching and sorting (68P10) Pattern recognition, speech recognition (68T10)

Related Items

LCS\(k\): a refined similarity measure, Unranked second-order anti-unification, The generalized definitions of the two-dimensional largest common substructure problems, Fast algorithms for computing tree LCS, Resequencing a set of strings based on a target string, A space efficient algorithm for the longest common subsequence in \(k\)-length substrings

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A survey on tree edit distance and related problems
• Kaikoura tree theorems: Computing the maximum agreement subtree
• A constrained edit distance between unordered labeled trees
• Fast parallel and serial multidimensional approximate array matching
• Constrained tree inclusion
• Simple Fast Algorithms for the Editing Distance between Trees and Related Problems
• Fast Algorithms for Finding Nearest Common Ancestors
• Maximum Agreement Subtree in a Set of Evolutionary Trees: Metrics and Efficient Algorithms
• The String-to-String Correction Problem
• Faster Scaling Algorithms for Network Problems
• Ordered and Unordered Tree Inclusion
• Combinatorial Pattern Matching
• Automata, Languages and Programming