Longest Common Subsequence in C++
In this post, we are going to discuss the longest common subsequence (time complexity and best solution in c++) which is briefly known as LCS in the dynamic programming area of the computer programming world. The LCS is a process to find the common longest sequence (a string of positional characters) in a set of strings according to the position of matching characters. Suppose s1 (news) and s2 (now) are two strings. The common characters of those strings (considering the position of characters in the string) are 'n' and 'w'. So, the LCS of s1 and s2 is 'nw' and the LCS length is 2.
Starting to write this content one thing is should be known that one of the dynamic programming purposes is to optimize the solution in the worst-case time complexity of a problem. So, the solution of the LCS problem on this page is the optimized best solution in a linear way than most of the content on the web.
You are here to copy the Longest Common Subsequence C++ code. So do it quickly. The code is below given. The description of this code is discussed after the code section. Also, the time complexity of this problem in C++ will be discussed.
#include<cstdio>
#include<algorithm>
using namespace std;
#define diag 1
#define up 2
#define left 3
int main()
{
string str1, str2, str;
int i, j, len1, len2;
cin>>str1;
cin>>str2;
len1=str1.size();
len2=str2.size();
int mat[len1+1][len2+1], d[len1+1][len2+1];//d for diagonal //+1 length initially is 0 to the row and column
for (i=0; i<=len1; i++)
{
mat[i][0]=0; //0 rows i th column all index 0
}
for (j=0; j<=len2; j++)
{
mat[0][j]=0; //0 column j th rows all index 0
}
for(i=1; i<=len1; i++)
{
for(j=1; j<=len2; j++)
{
if(str1[i-1]==str2[j-1])
{
mat[i][j]=mat[i-1][j-1]+1;
d[i][j]=diag;
}
else
{
mat[i][j]=max(mat[i-1][j], mat[i][j-1]);
if(mat[i][j]==mat[i-1][j])
d[i][j]=up;
else
d[i][j]=left;
}
}
}
cout<<"LCS length: "<<mat[len1][len2]<<endl;
i=len1;
j=len2;
str="";
while(i>0 && j>0)
{
if(d[i][j]==diag)
{
str+=str1[i-1];
i--;
j--;
}
else if(d[i][j]==up)
{
i--;
}
else
{
j--;
}
}
reverse(str.begin(), str.end());
cout<<"LCS string: "<<str<<endl;
return 0;
}
Sample Input:
news
now
Sample Output:
LCS length: 2
LCS string: nw
There are two popular solutions on the web for LCS. It can be solved using the Recursive way and Linear way. If string s1 is considered as 'm' length and s2 are considered as 'n' length. Then, the time complexity in a recursive way for this problem is O(n*n). The time complexity can be minimized using a linear way solution. This problem's best solution is available in a linear way, which is O(mn). The above solution is solved in a linear way.
Time Complexity of LCS in Linear way
Time Complexity of LCS in Recursive way
