The longest common subsequence (LCS) problem asks for the longest sequence that is a subsequence of every sequence in a given set, most often just two sequences; unlike a common substring, the elements of a common subsequence need not occupy consecutive positions in the original sequences. It is a classic computer science problem, solvable in polynomial time for a fixed number of sequences by dynamic programming, though the general problem with an arbitrary number of sequences is NP-hard. LCS has practical applications in file comparison utilities such as diff, revision control systems, computational linguistics and bioinformatics. This description is adapted from Wikipedia contributors under CC BY-SA 4.0; changes were made. https://creativecommons.org/licenses/by-sa/4.0/
Facts
Time ComplexityO(n times m) by dynamic programming for two sequences of length n and m; NP-hard for an arbitrary number of sequences. 1 Classification
Design Technique Sources
1. Wikipedia: Longest Common Subsequence Algorithm
Wikimedia FoundationLead section
A longest common subsequence (LCS) is the longest subsequence common to all sequences in a set of sequences (often just two sequences). It differs from the longest common substring: unlike substrings, elements of subsequences are not required to occupy consecutive positions within the original sequences.
Body, complexity discussion
For two sequences of lengths n and m, the dynamic programming approach runs in O(n x m) time.
entity record, description (design-technique)
It is a classic computer science problem, solvable in polynomial time for a fixed number of sequences by dynamic programming, though the general problem with an arbitrary number of sequences is NP-hard.
View the Source Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.