Scribd
Upload
9 views7 pages

Longest Common Subsequence Explained

The Longest Common Subsequence (LCS) problem identifies the longest subsequence present in two sequences, which maintains the same relative order. The document outlines a dynamic programming approach to solve the LCS problem, providing recurrence relations and implementation details. Applications of LCS include version control systems, plagiarism detection, DNA sequencing, and data compression, with a time and space complexity of O(m × n).

Uploaded by

shaikmadihazufa138
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
9 views7 pages

Longest Common Subsequence Explained

The Longest Common Subsequence (LCS) problem identifies the longest subsequence present in two sequences, which maintains the same relative order. The document outlines a dynamic programming approach to solve the LCS problem, providing recurrence relations and implementation details. Applications of LCS include version control systems, plagiarism detection, DNA sequencing, and data compression, with a time and space complexity of O(m × n).

Uploaded by

shaikmadihazufa138
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd

Longest Common Subsequence

Using Dynamic Programming

Presented by: Meghraj & Moka


What is LCS?
The Longest Common Subsequence (LCS) problem finds the longest subsequence
present in both sequences.

Key Point: A subsequence is a sequence that appears in the same relative order, but not
necessarily contiguous.

Example 1: Example 2:
String 1: ABCDGH String 1: AGGTAB
String 2: AEDFHR String 2: GXTXAYB
LCS: ADH (length 3) LCS: GTAB (length 4)
DP Algorithm
Recurrence Relation: Implementation:
int lcs(string s1, string s2) {
int m = [Link]();
int n = [Link]();
If characters match: int dp[m+1][n+1];
dp[i][j] = dp[i-1][j-1] + 1
for(int i=0; i<=m; i++) {
for(int j=0; j<=n; j++) {
If characters don't match: if(i==0 || j==0)
dp[i][j] = max(dp[i-1][j], dp[i][j- dp[i][j] = 0;
1]) else if(s1[i-1] == s2[j-1])
dp[i][j] = dp[i-1][j-1] + 1;
else
dp[i][j] = max(dp[i-1][j],
dp[i][j-1]);
}
}
return dp[m][n];
}
Example: "stone" vs "longest"
String 1: STONE String 2: LONGEST

Longest Common Subsequence: "ON"


LCS Length: 2
Applications of LCS
🔍 Diff Tools 🧬 DNA Sequencing

Git, SVN, and version control systems use LCS to find Comparing genetic sequences to find similarities and
differences between file versions. evolutionary relationships.

📄 Plagiarism Detection 💬 Text Editors

Identifying common subsequences in documents to detect Auto-completion, spell checking, and finding similar words or
copied content. phrases.

🎬 Data Compression 🔤 String Matching

Finding repeated patterns in data for efficient compression Pattern matching, fuzzy search, and approximate string
algorithms. matching.
Time & Space Complexity

Time Complexity

O(m × n)
where m and n are the lengths of the two strings

Space Complexity

O(m × n)
Thank You!
Presented by: Meghraj & Moka

You might also like