A new efficient algorithm for computing the longest common subsequence

DOI10.1007/S00224-008-9101-6MaRDI QIDQ733720zbMATH OpenOpenAlexFDO

Authors Costas S. Iliopoulos, M. Sohel Rahman

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

algorithmslongest common subsequencestrings

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05)

Recommendations

• A New Efficient Algorithm for Computing the Longest Common Subsequence
• An efficient algorithm for LCS problem between two arbitrary sequences
• The longest common subsequence problem -- a finite automata approach
• New efficient algorithms for the LCS and constrained LCS problems
• A new practical linear space algorithm for the longest common subsequence problem

Cites work

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

Cited in

(36)

• A Linear-Time n ^0.4 -Approximation for Longest Common Subsequence
• A data structure for substring-substring LCS length queries
• scientific article; zbMATH DE number 842125 (Why is no real title available?)
• scientific article; zbMATH DE number 7561345 (Why is no real title available?)
• A fast and simple algorithm for computing the longest common subsequence of run-length encoded strings
• Algorithms for computing variants of the longest common subsequence problem
• scientific article; zbMATH DE number 88968 (Why is no real title available?)
• Computing longest common square subsequences
• Algorithms for Computing Variants of the Longest Common Subsequence Problem
• Computing a longest common palindromic subsequence
• String Processing and Information Retrieval
• An efficient algorithm for LCS problem between two arbitrary sequences
• Algorithms and hardness for the longest common subsequence of three strings and related problems
• Efficient merged longest common subsequence algorithms for similar sequences
• Efficient algorithms for the longest common subsequence in \(k\)-length substrings
• A specialized branching and fathoming technique for the longest common subsequence problem
• Computing a longest common subsequence that is almost increasing on sequences having no repeated elements
• Fundamentals of Computation Theory
• An efficient dynamic programming algorithm for the generalized LCS problem with multiple substring exclusive constraints
• Efficient algorithms for the longest common subsequence problem with sequential substring constraints
• scientific article; zbMATH DE number 5545474 (Why is no real title available?)
• Solving longest common subsequence problems via a transformation to the maximum clique problem
• A dynamic programming solution to a generalized LCS problem
• Efficient polynomial-time algorithms for the constrained LCS problem with strings exclusion
• The longest common subsequence problem -- a finite automata approach
• Computing the longest common almost-increasing subsequence
• New tabulation and sparse dynamic programming based techniques for sequence similarity problems
• Computing the longest common subsequence of two run-length encoded strings
• A New Efficient Algorithm for Computing the Longest Common Subsequence
• Constrained sequence analysis algorithms in computational biology
• A simple algorithm for solving for the generalized longest common subsequence (LCS) problem with a substring exclusion constraint
• FACC: a novel finite automaton based on cloud computing for the multiple longest common subsequences search
• A learning algorithm for the longest common subsequence problem
• Palindromic subsequence automata and longest common palindromic subsequence
• An efficient systolic algorithm for the longest common subsequence problem
• A Scalable Approximation Algorithm for Weighted Longest Common Subsequence

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

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