Longest Common Subsequence (LCS) using Recursion
Generate all the possible subsequences and find the longest among them that is present in both strings using recursion.
Follow the below steps to implement the idea:
- Create a recursive function [say lcs()].
- Check the relation between the First characters of the strings that are not yet processed.
- Depending on the relation call the next recursive function as mentioned above.
- Return the length of the LCS received as the answer.
Below is the implementation of the recursive approach:
// A Naive recursive implementation of LCS problem
#include <bits/stdc++.h>
using namespace std;
// Returns length of LCS for X[0..m-1], Y[0..n-1]
int lcs(string X, string Y, int m, int n)
{
if (m == 0 || n == 0)
return 0;
if (X[m - 1] == Y[n - 1])
return 1 + lcs(X, Y, m - 1, n - 1);
else
return max(lcs(X, Y, m, n - 1),
lcs(X, Y, m - 1, n));
}
// Driver code
int main()
{
string S1 = "AGGTAB";
string S2 = "GXTXAYB";
int m = S1.size();
int n = S2.size();
cout << "Length of LCS is " << lcs(S1, S2, m, n);
return 0;
}
// This code is contributed by rathbhupendra
// A Naive recursive implementation
// of LCS problem
#include <stdio.h>
int max(int a, int b);
// Returns length of LCS for X[0..m-1],
// Y[0..n-1]
int lcs(char* X, char* Y, int i, int j)
{
if (X[i] == 0 || Y[j] == 0)
return 0;
if (X[i] == Y[j])
return 1 + lcs(X, Y, i + 1, j + 1);
else
return max(lcs(X, Y, i, j + 1),
lcs(X, Y, i + 1, j));
}
// Utility function to get max of
// 2 integers
int max(int a, int b) { return (a > b) ? a : b; }
// Driver code
int main()
{
char S1[] = "BD";
char S2[] = "ABCD";
int m = strlen(S1);
int n = strlen(S2);
int i = 0, j = 0;
// Function Call
printf("Length of LCS is %d", lcs(S1, S2, i, j));
return 0;
}
// A Naive recursive implementation of LCS problem in java
import java.io.*;
import java.util.*;
public class LongestCommonSubsequence {
// Returns length of LCS for X[0..m-1], Y[0..n-1]
int lcs(String X, String Y, int m, int n)
{
if (m == 0 || n == 0)
return 0;
if (X.charAt(m - 1) == Y.charAt(n - 1))
return 1 + lcs(X, Y, m - 1, n - 1);
else
return max(lcs(X, Y, m, n - 1),
lcs(X, Y, m - 1, n));
}
// Utility function to get max of 2 integers
int max(int a, int b) { return (a > b) ? a : b; }
// Driver code
public static void main(String[] args)
{
LongestCommonSubsequence lcs
= new LongestCommonSubsequence();
String S1 = "AGGTAB";
String S2 = "GXTXAYB";
int m = S1.length();
int n = S2.length();
System.out.println("Length of LCS is"
+ " " + lcs.lcs(S1, S2, m, n));
}
}
// This Code is Contributed by Saket Kumar
# A Naive recursive Python implementation of LCS problem
def lcs(X, Y, m, n):
if m == 0 or n == 0:
return 0
elif X[m-1] == Y[n-1]:
return 1 + lcs(X, Y, m-1, n-1)
else:
return max(lcs(X, Y, m, n-1), lcs(X, Y, m-1, n))
# Driver code
if __name__ == '__main__':
S1 = "AGGTAB"
S2 = "GXTXAYB"
print("Length of LCS is", lcs(S1, S2, len(S1), len(S2)))
// C# Naive recursive implementation of LCS problem
using System;
class GFG {
// Returns length of LCS for X[0..m-1], Y[0..n-1]
static int lcs(String X, String Y, int m, int n)
{
if (m == 0 || n == 0)
return 0;
if (X[m - 1] == Y[n - 1])
return 1 + lcs(X, Y, m - 1, n - 1);
else
return max(lcs(X, Y, m, n - 1),
lcs(X, Y, m - 1, n));
}
// Utility function to get max of 2 integers
static int max(int a, int b) { return (a > b) ? a : b; }
// Driver code
public static void Main()
{
String S1 = "AGGTAB";
String S2 = "GXTXAYB";
int m = S1.Length;
int n = S2.Length;
Console.Write("Length of LCS is"
+ " " + lcs(S1, S2, m, n));
}
}
// This code is Contributed by Sam007
<script>
// A Naive recursive implementation of LCS problem in java
// Returns length of LCS for X[0..m-1], Y[0..n-1]
function lcs( X, Y , m , n )
{
if (m == 0 || n == 0)
return 0;
if (X[m-1] == Y[n-1])
return 1 + lcs(X, Y, m-1, n-1);
else
return max(lcs(X, Y, m, n-1), lcs(X, Y, m-1, n));
}
// Utility function to get max of 2 integers
function max(a , b)
{
return (a > b)? a : b;
}
var s1 = "AGGTAB";
var s2 = "GXTXAYB";
var X = s1;
var Y = s2;
var m = X.length;
var n = Y.length;
document.write("Length of LCS is" + " " +
lcs( X, Y, m, n ) );
// This code contributed by umadevi9616
</script>
<?php
// A Naive recursive PHP
// implementation of LCS problem
function lcs($X, $Y, $m, $n)
{
if($m == 0 || $n == 0)
return 0;
else if ($X[$m - 1] == $Y[$n - 1])
return 1 + lcs($X, $Y,
$m - 1, $n - 1);
else
return max(lcs($X, $Y, $m, $n - 1),
lcs($X, $Y, $m - 1, $n));
}
// Driver Code
$S1 = "AGGTAB";
$S2 = "GXTXAYB";
echo "Length of LCS is ";
echo lcs($S1 , $S2, strlen($S1),
strlen($S2));
// This code is contributed
// by Shivi_Aggarwal
?>
Output
Length of LCS is 4
Time Complexity: O(2m+n)
Auxiliary Space: O(1)
Longest Common Subsequence (LCS)
Given two strings, S1 and S2, the task is to find the length of the Longest Common Subsequence, i.e. longest subsequence present in both of the strings.
A longest common subsequence (LCS) is defined as the longest subsequence which is common in all given input sequences.
Examples:
Input: S1 = “ABC”, S2 = “ACD”
Output: 2
Explanation: The longest subsequence which is present in both strings is “AC”.Input: S1 = “AGGTAB”, S2 = “GXTXAYB”
Output: 4
Explanation: The longest common subsequence is “GTAB”.Input: S1 = “ABC”, S2 = “CBA”
Output: 1
Explanation: There are three common subsequences of length 1, “A”, “B” and “C” and no common subsequence.of length more than 1.Input: S1 = “XYZW”, S2 = “XYWZ”
Output: 3
Explanation: There are two common subsequences of length 3 “XYZ”, and”XYW”, and no common subsequence. of length more than 3.
Contact Us