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. 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.