Longest Common Subsequence in C++ using Recursion

In this tutorial, we will learn about how to find the longest common subsequence (LCS) in C++ by using recursion. We will also see the code implementation in c++ to find the longest common subsequence.

We will also see examples to understand the concept in a better way.

You can also have a look at this: Longest Increasing Subsequence in C++

Longest Common Subsequence using Recursion

A subsequence is a sequence that appears in relative order, but not necessarily contiguous.

In the longest common subsequence problem,

We have given two sequences, so we need to find out the longest subsequence present in both of them.

Let’s see the examples,

string_1="abcdef"
string_2="xyczef"
So, length of LCS is 3. Hence common subsequence is "cef".

string_1="ahkolp"
string_2="ehyozp"
So, length of LCS is 3. Hence common subsequence is "hop".

By the help of the above examples, we can understand the LCS.

Now, let’s see the pseudocode for recursive approach,

1.let m and n is the length of two string s1 and s2.
2.LongestCommonSubsequence( string X, string Y, int m, int n )  
   if m == 0 || n == 0 then do 
      return 0;  
   if X[m-1] == Y[n-1] then do
      return 1 + LongestCommonSubsequence(X, Y, m-1, n-1);  
   else
      return max(LongestCommonSubsequence(X, Y, m, n-1), LongestCommonSubsequence(X, Y, m-1, n));    

Let’s see the 2d array filling structure for a better understanding,

  0 a b c d e f
0 0 0 0 0 0 0 0
x 0 0 0 0 0 0 0
y 0 0 0 0 0 0 0
c 0 0 0 1 1 1 1
z 0 0 0 1 1 1 1
e 0 0 0 1 1 2 2
f 0 0 0 1 1 2 3  hence LCS is 3.

Code implementation in C++: Longest Common Subsequence

#include<bits/stdc++.h> 
using namespace std; 
int LongestCommonSubsequence( string X, string Y, int m, int n )  
{  
    if (m == 0 || n == 0)  
        return 0;  
    if (X[m-1] == Y[n-1])  
        return 1 + LongestCommonSubsequence(X, Y, m-1, n-1);  
    else
        return max(LongestCommonSubsequence(X, Y, m, n-1), LongestCommonSubsequence(X, Y, m-1, n));  
}  
int main() { 
  string s1="abcdef";
  string s2="xyczef"; 
  int a=s1.length(); 
  int b=s2.length();
  cout<<"Longest common subsequence is:"<<" ";
  cout<<LongestCommonSubsequence(s1,s2,a,b);
  return 0;
}

Output

LCS of given strings is: 3

You may also learn,

Solution of N-Queen problem in C++ using Backtracking

Activity Selection Problem using Greedy method in C++