concept · INFO-CS-ADS-177Longest Common Subsequence (LCS)
Learn how dynamic programming finds the longest sequence of elements shared by two sequences while preserving their relative order.
Explanation
Overview
The Longest Common Subsequence problem finds the longest sequence that appears in two given sequences in the same relative order. The selected elements do not need to be adjacent in either original sequence.
Key concepts
Subsequence; Prefix-based states; Matching elements; Optimal substructure; Table reconstruction
Variables
X: The first input sequence.; Y: The second input sequence.; i: The number of elements considered from X.; j: The number of elements considered from Y.; dp[i][j]: The length of the LCS of the first i and first j elements.
Complexity
tabulation: O(mn) time and O(mn) space.; spaceOptimized: O(mn) time and O(min(m,n)) space when only the length is required.; variables: m and n are the lengths of the two input sequences.
Example
sequenceX: ABCBDAB; sequenceY: BDCABA; oneLongestCommonSubsequence: BCBA; length: 4; explanation: The characters B, C, B, and A appear in both sequences in the same relative order, even though they are not necessarily adjacent.
Pseudocode
function LCS(X, Y):
m = length(X)
n = length(Y)
dp = 2D array of size (m + 1) × (n + 1) filled with 0
for i = 1 to m:
for j = 1 to n:
if X[i - 1] == Y[j - 1]:
dp[i][j] = 1 + dp[i - 1][j - 1]
else:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
return dp[m][n]
Applications
Text comparison.; Version-control diff tools.; DNA and protein sequence analysis.; Similarity measurement.; File comparison.
Variables
X
The first input sequence.
Y
The second input sequence.
I
The number of elements considered from X.
J
The number of elements considered from Y.
Dp[i][j]
The length of the LCS of the first i and first j elements.
Example or application
One Longest Common Subsequence
BCBA
Explanation
The characters B, C, B, and A appear in both sequences in the same relative order, even though they are not necessarily adjacent.
Definition
The Longest Common Subsequence problem finds the longest sequence that appears in two given sequences in the same relative order. The selected elements do not need to be adjacent in either original sequence.
Mathematical Representation
If X[i-1] = Y[j-1], dp[i][j] = 1 + dp[i-1][j-1]; otherwise dp[i][j] = max(dp[i-1][j], dp[i][j-1]).
Approaches
Recursive
Compares the final elements of the two prefixes and explores smaller prefix combinations.
Memoization
Stores previously calculated prefix-pair results.
Tabulation
Builds a two-dimensional table from empty prefixes toward the complete sequences.
Reconstruction
Traces backward through the table to recover one longest common subsequence.
Pseudocode
function LCS(X, Y):
m = length(X)
n = length(Y)
dp = 2D array of size (m + 1) × (n + 1) filled with 0
for i = 1 to m:
for j = 1 to n:
if X[i - 1] == Y[j - 1]:
dp[i][j] = 1 + dp[i - 1][j - 1]
else:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
return dp[m][n]
Complexity
Tabulation
O(mn) time and O(mn) space.
Space Optimized
O(mn) time and O(min(m,n)) space when only the length is required.
Variables
m and n are the lengths of the two input sequences.
Key Concepts
Subsequence
Prefix-based states
Matching elements
Optimal substructure
Table reconstruction
Advantages
Finds the longest order-preserving shared sequence.
Supports text comparison and sequence analysis.
Can reconstruct an actual common subsequence.
Demonstrates two-dimensional dynamic programming.
Limitations
The standard table requires O(mn) time and memory.
Large sequences may make the full table expensive.
Multiple different longest common subsequences may exist.
Practice Question
What is the length of an LCS for ABC and AC?
Practice Answer
2. One longest common subsequence is AC.
Learning Objectives
Explain the central idea and purpose of longest common subsequence (lcs).
Identify the assumptions, inputs, and conditions relevant to longest common subsequence (lcs).
Evaluate an application of longest common subsequence (lcs) for correctness and practical resource requirements.
Sources and verification
Sources are shown as provided in the project data. Not every source has yet been independently verified. Please report errors or missing citations.
- Dynamic Programming Applications
Suggest a correction or source · More in Algorithms & Data Structures