A new efficient algorithm for computing the longest common subsequence

DOI10.1007/S00224-008-9101-6zbMATH Open1187.68681OpenAlexW2092011338MaRDI QIDQ733720FDOQ733720

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

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

zbMATH Keywords

algorithmslongest common subsequencestrings

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05)

Cites Work

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

Cited In (31)

• Title not available (Why is that?)
• Title not available (Why is that?)
• Computing a longest common subsequence that is almost increasing on sequences having no repeated elements
• A simple algorithm for solving for the generalized longest common subsequence (LCS) problem with a substring exclusion constraint
• A Scalable Approximation Algorithm for Weighted Longest Common Subsequence
• Palindromic subsequence automata and longest common palindromic subsequence
• An efficient systolic algorithm for the longest common subsequence problem
• A data structure for substring-substring LCS length queries
• Title not available (Why is that?)
• Solving longest common subsequence problems via a transformation to the maximum clique problem
• Algorithms for Computing Variants of the Longest Common Subsequence Problem
• A fast and simple algorithm for computing the longest common subsequence of run-length encoded strings
• Title not available (Why is that?)
• 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 algorithms for the longest common subsequence problem with sequential substring constraints
• Efficient algorithms for the longest common subsequence in \(k\)-length substrings
• Computing the longest common almost-increasing subsequence
• A Linear-Time n ^0.4 -Approximation for Longest Common Subsequence
• String Processing and Information Retrieval
• A specialized branching and fathoming technique for the longest common subsequence problem
• Algorithms for computing variants of the longest common subsequence problem
• Fundamentals of Computation Theory
• Efficient polynomial-time algorithms for the constrained LCS problem with strings exclusion
• A New Efficient Algorithm for Computing the Longest Common Subsequence
• Efficient merged longest common subsequence algorithms for similar sequences
• 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
• Title not available (Why is that?)
• Algorithms and hardness for the longest common subsequence of three strings and related problems
• Constrained sequence analysis algorithms in computational biology

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)