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.
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. 2 Classification
Design Technique Time Complexity
Time Complexity (category)Quadratic Time -- O(n^2) 1 Connections
Sources
1. Longest Common Subsequence Algorithm (Wikipedia)
Wikipedia infobox: time complexity quadratic
quadratic
Wikipedia: design technique dynamic-programming
dynamic-programming
View the Source2. 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.
Complexity
For the general case of an arbitrary number of input sequences, the problem is NP-hard. When the number of sequences is constant, the problem is solvable in polynomial time by dynamic programming.
In Group: Edit Distance and Sequence Alignment Algorithms, Lead
A longest common subsequence (LCS) is the longest subsequence common to all sequences in a set of sequences (often just two sequences).
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.