A new efficient algorithm for computing the longest common subsequence

DOI10.1007/s00224-008-9101-6zbMath1187.68681OpenAlexW2092011338MaRDI QIDQ733720

M. Sohel Rahman, Costas S. Iliopoulos

Publication date: 19 October 2009

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00224-008-9101-6

zbMATH Keywords

algorithmsstringslongest common subsequence

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05)

Related Items (13)

Palindromic subsequence automata and longest common palindromic subsequence ⋮ Computing the longest common almost-increasing subsequence ⋮ Solving longest common subsequence problems via a transformation to the maximum clique problem ⋮ Computing a longest common subsequence that is almost increasing on sequences having no repeated elements ⋮ A Linear-Time n ^0.4 -Approximation for Longest Common Subsequence ⋮ A dynamic programming solution to a generalized LCS problem ⋮ An efficient dynamic programming algorithm for the generalized LCS problem with multiple substring exclusive constraints ⋮ Efficient polynomial-time algorithms for the constrained LCS problem with strings exclusion ⋮ A simple algorithm for solving for the generalized longest common subsequence (LCS) problem with a substring exclusion constraint ⋮ Constrained sequence analysis algorithms in computational biology ⋮ Unnamed Item ⋮ Unnamed Item ⋮ A data structure for substring-substring LCS length queries

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Algorithms for computing variants of the longest common subsequence problem
• New efficient algorithms for the LCS and constrained LCS problems
• The constrained longest common subsequence problem
• An \(O(ND)\) difference algorithm and its variations
• A faster algorithm computing string edit distances
• A longest common subsequence algorithm suitable for similar text strings
• Preserving order in a forest in less than logarithmic time and linear space
• A fast algorithm for computing longest common subsequences
• The Complexity of Some Problems on Subsequences and Supersequences
• Algorithms for the Longest Common Subsequence Problem
• The String-to-String Correction Problem
• On the Approximation of Shortest Common Supersequences and Longest Common Subsequences
• Faster Algorithms for Computing Longest Common Increasing Subsequences
• A New Efficient Algorithm for Computing the Longest Common Subsequence
• Algorithms for Computing Variants of the Longest Common Subsequence Problem
• Transposition invariant string matching
• Combinatorial Pattern Matching
• ALGORITHMS FOR THE CONSTRAINED LONGEST COMMON SUBSEQUENCE PROBLEMS

This page was built for publication: A new efficient algorithm for computing the longest common subsequence