Longest Common Subsequence(LCS) Simplified and solution using Dynamic Programming with code also
Longest Common Subsequence type problems have two sequences (set of characters or strings) are given ,We have to find the longest possible subsequence which is common in both the sequences.
What is Subsequence ?
A subsequence is a sequence that appears in the same relative order, but not necessarily contiguous.So we can skip some character in the sequence inorder to make the common subsequence.
-Path crossing in comparing is not allowed as they are in relative order.
- Example how we should compare.
LCS can be solved in many ways like brute force approach,recursive approach but the best and easy to implement way is dynamic programming so we will use it here for solving our problems.
How to solve ?
In dynamic programming we use memorization for which we implement a matrix containing both sequence to compare.one sequence in columns and one rows.
Our 0th column and row will be default zero.We can say rows as i and columns as j .lets say our matrix name is LCS. We start comparing the the first row element with the first column element and check for the conditions.
Mainly two conditions we have to check for filling a value in the matrix.
(1)If both are equal: if(i==j)
We add one in the diagonal element from upper and put the value in the matrix at the location of (i,j).
LCS[i,j]=1+LCS[i-1,j-1].
(2) If both are not equal:else
We simply add use the value of the max from immediate upper element or immediate left side element.
LCS[i,j]=max( LCS[i-1,j], LCS[i,j-1]).
same way we will apply these conditions to find all the elements of the matrix.
Let us take one example:
String 1: ABCD
String 2: BD
here we call columns as j and rows as i of the matrix.
Step 1: Initially We have the 0th row and column 0.
Step 2 : Now we start at i=1 and compare it with j=1 so here B and A are not equal so 2nd condition is applied and max from upper or left side is selected here its 0 so put it in the matrix location LCS[1,1].
Step 3:Same way compare the i=1 with j=2 here both are equal so condition one is applied and 1+diagonal element is filled in matrix.
Step 4: same way fill the whole matrix which will look like:
Here from last element LCS[2,4] we can have the length of the longest subsequence.
How to find the subsequence ?
Here we start from last node and go to previous node from which the current value came from after applying condition till the 0th row it is our path.
Here last element is LCS[2,4]=2 which came from diagonal element LCS[1,3]=1 cause the i and j are equal so reach there and again find the elements came from here it came from left side element LCS[1,2] so reach there now it came from diagonal 0th row element 0 so stop.
Now in our path whenever there is upward side arrow consider that for our subsequence (start from left to right) so here first upward arrow came from LCS[1,2] so add B in our subsequence same way also add D so finally our longest common subsequence is BD.
Here is my code for LCS:
#include<iostream>
#include<string.h>
using namespace std;
//MARVIN RAVAL
int main()
{ string str1,str2;
cin>>str1;
cin>>str2;
int m,n;
string store;
int k=0;
m=str1.length();
n=str2.length();
int matrix[m+1][n+1];
int i;
for(i=0;i<=m;i++)
{ matrix[i][0]=0;
}
for(i=0;i<=n;i++)
{ matrix[0][i]=0;
}
for(i=1;i<=m;i++)
{ for(int j=1;j<=n;j++)
{
if(str1[i-1]==str2[j-1])
{ matrix[i][j]=1+matrix[i-1][j-1];
}
else{
matrix[i][j]=max(matrix[i-1][j],matrix[i][j-1]);
}
}
}
for(i=0;i<=m;i++)
{ for(int j=0;j<=n;j++)
{
cout<<matrix[i][j]<<” “;
}
cout<<” “<<endl;
}
for(i=1;i<=m;i++)
{ for(int j=1;j<=n;j++)
{ if(matrix[i][j]-matrix[i-1][j-1]==1 && matrix[i][j]!=matrix[i-1][j] && matrix[i][j]!=matrix[i][j-1])
{
//MARVIN RAVAL
store=store+str1[i-1];
}
}
}
cout<<store;
}
OUTPUT:
Complexity:
To populate the table, the outer for loop iterates m times and the inner for loop iterates n times. Hence, the complexity of the algorithm is O(m, n), where m and n are the length of two strings.
USES:
→ It is widely used in computational linguistics and bioinformatics.
→ It is also widely used by revision control systems such as Git for reconciling multiple changes made to a revision-controlled collection of files.
→In searching and authentication.
→Plagiarism is one of the biggest use of LCS.
Thats it for LCS.
if you found the post helpful follow and clap for future posts.
