Posted on by Kalkicode
Code Backtracking

# Longest common subsequence

In computer science, a subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements. The longest common subsequence (LCS) of two or more sequences is the longest subsequence that is present in all the given sequences in the same relative order.

For example, let's consider two sequences: "ACBDEA" and "ABCDA". The common subsequences are "A", "B", "C", "D", "E", "AB", "AC", "AD", "AE", "BC", "BD", and "DA". Out of these subsequences, the longest common subsequence is "ABDA", which appears in both the given sequences in the same order.

The problem of finding the longest common subsequence is a well-studied problem in computer science, and it has applications in fields such as bioinformatics, data compression, and version control systems.

## Program Solution

``````// C Program
// Longest common subsequence
#include <stdio.h>
#include <string.h>

// Returns the max value of given two numbers
int maxValue(int a, int b)
{
if (a > b)
{
return a;
}
else
{
return b;
}
}
// Returns the length of common substring
int lcs(const char *s1 , const char *s2, int n1, int n2, int i, int j)
{
if (i == n1 || j == n2)
{
// When string length exceeds
return 0;
}
else if (s1[i] == s2[j])
{
// When similar characters meet
return 1 + lcs(s1, s2, n1, n2, i + 1, j + 1);
}
else
{
// Through recursively find similar characters
return maxValue(lcs(s1, s2, n1, n2, i + 1, j), lcs(s1, s2, n1, n2, i, j + 1));
}
}
int main(int argc, char
const *argv[])
{
const char *s1 = "AABCAEGDS";
// Get the size of string
int n1 = strlen(s1);
int n2 = strlen(s2);
int ans = lcs(s1, s2, n1, n2, 0, 0);
// Display length of common substring
printf("\n %d\n", ans);
return 0;
}``````

#### Output

`` 4``
``````/*
Java Program for
Longest common subsequence
*/
class LongestSubsequence
{
// Returns the max value of given two numbers
public int maxValue(int a, int b)
{
if (a > b)
{
return a;
}
else
{
return b;
}
}
// Returns the length of common substring
public int lcs(String s1, String s2, int n1, int n2, int i, int j)
{
if (i == n1 || j == n2)
{
// When string length exceeds
return 0;
}
else if (s1.charAt(i) == s2.charAt(j))
{
// When similar characters meet
return 1 + lcs(s1, s2, n1, n2, i + 1, j + 1);
}
else
{
// Through recursively find similar characters
return maxValue(lcs(s1, s2, n1, n2, i + 1, j), lcs(s1, s2, n1, n2, i, j + 1));
}
}
public static void main(String[] args)
{
String s1 = "AABCAEGDS";
// Get the size of string
int n1 = s1.length();
int n2 = s2.length();
int ans = task.lcs(s1, s2, n1, n2, 0, 0);
// Display length of common substring
System.out.print("\n " + ans + "\n");
}
}``````

#### Output

`` 4``
``````// Include header file
#include <iostream>
#include<string.h>
using namespace std;
/*
C++ Program for
Longest common subsequence
*/
class LongestSubsequence
{
public:
// Returns the max value of given two numbers
int maxValue(int a, int b)
{
if (a > b)
{
return a;
}
else
{
return b;
}
}
// Returns the length of common substring
int lcs(string s1, string s2, int n1, int n2, int i, int j)
{
if (i == n1 || j == n2)
{
// When string length exceeds
return 0;
}
else if (s1[i] == s2[j])
{
// When similar characters meet
return 1 + this->lcs(s1, s2, n1, n2, i + 1, j + 1);
}
else
{
// Through recursively find similar characters
return this->maxValue(this->lcs(s1, s2, n1, n2, i + 1, j), this->lcs(s1, s2, n1, n2, i, j + 1));
}
}
};
int main()
{
string s1 = "AABCAEGDS";
// Get the size of string
int n1 = s1.size();
int n2 = s2.size();
int ans = task.lcs(s1, s2, n1, n2, 0, 0);
// Display length of common substring
cout << "\n " << ans << "\n";
return 0;
}``````

#### Output

`` 4``
``````// Include namespace system
using System;
/*
C# Program for
Longest common subsequence
*/
public class LongestSubsequence
{
// Returns the max value of given two numbers
public int maxValue(int a, int b)
{
if (a > b)
{
return a;
}
else
{
return b;
}
}
// Returns the length of common substring
public int lcs(String s1, String s2, int n1, int n2, int i, int j)
{
if (i == n1 || j == n2)
{
// When string length exceeds
return 0;
}
else if (s1[i] == s2[j])
{
// When similar characters meet
return 1 + lcs(s1, s2, n1, n2, i + 1, j + 1);
}
else
{
// Through recursively find similar characters
return maxValue(lcs(s1, s2, n1, n2, i + 1, j), lcs(s1, s2, n1, n2, i, j + 1));
}
}
public static void Main(String[] args)
{
String s1 = "AABCAEGDS";
// Get the size of string
int n1 = s1.Length;
int n2 = s2.Length;
int ans = task.lcs(s1, s2, n1, n2, 0, 0);
// Display length of common substring
Console.Write("\n " + ans + "\n");
}
}``````

#### Output

`` 4``
``````<?php
/*
Php Program for
Longest common subsequence
*/
class LongestSubsequence
{
// Returns the max value of given two numbers
public	function maxValue(\$a, \$b)
{
if (\$a > \$b)
{
return \$a;
}
else
{
return \$b;
}
}
// Returns the length of common substring
public	function lcs(\$s1, \$s2, \$n1, \$n2, \$i, \$j)
{
if (\$i == \$n1 || \$j == \$n2)
{
// When string length exceeds
return 0;
}
else if (\$s1[\$i] == \$s2[\$j])
{
// When similar characters meet
return 1 + \$this->lcs(\$s1, \$s2, \$n1, \$n2, \$i + 1, \$j + 1);
}
else
{
// Through recursively find similar characters
return \$this->maxValue(\$this->lcs(\$s1, \$s2, \$n1, \$n2, \$i + 1, \$j), \$this->lcs(\$s1, \$s2, \$n1, \$n2, \$i, \$j + 1));
}
}
}

function main()
{
\$s1 = "AABCAEGDS";
// Get the size of string
\$n1 = strlen(\$s1);
\$n2 = strlen(\$s2);
\$ans = \$task->lcs(\$s1, \$s2, \$n1, \$n2, 0, 0);
// Display length of common substring
echo "\n ". \$ans ."\n";
}
main();``````

#### Output

`` 4``
``````/*
Node Js Program for
Longest common subsequence
*/
class LongestSubsequence
{
// Returns the max value of given two numbers
maxValue(a, b)
{
if (a > b)
{
return a;
}
else
{
return b;
}
}
// Returns the length of common substring
lcs(s1, s2, n1, n2, i, j)
{
if (i == n1 || j == n2)
{
// When string length exceeds
return 0;
}
else if (s1[i] == s2[j])
{
// When similar characters meet
return 1 + this.lcs(s1, s2, n1, n2, i + 1, j + 1);
}
else
{
// Through recursively find similar characters
return this.maxValue(this.lcs(s1, s2, n1, n2, i + 1, j), this.lcs(s1, s2, n1, n2, i, j + 1));
}
}
}

function main()
{
var s1 = "AABCAEGDS";
// Get the size of string
var n1 = s1.length;
var n2 = s2.length;
var ans = task.lcs(s1, s2, n1, n2, 0, 0);
// Display length of common substring
process.stdout.write("\n " + ans + "\n");
}
main();``````

#### Output

`` 4``
``````#   Python 3 Program for
#   Longest common subsequence

class LongestSubsequence :
#  Returns the max value of given two numbers
def maxValue(self, a, b) :
if (a > b) :
return a
else :
return b

#  Returns the length of common substring
def lcs(self, s1, s2, n1, n2, i, j) :
if (i == n1 or j == n2) :
#  When string length exceeds
return 0

elif(s1[i] == s2[j]) :
#  When similar characters meet
return 1 + self.lcs(s1, s2, n1, n2, i + 1, j + 1)
else :
#  Through recursively find similar characters
return self.maxValue(self.lcs(s1, s2, n1, n2, i + 1, j), self.lcs(s1, s2, n1, n2, i, j + 1))

def main() :
s1 = "AABCAEGDS"
#  Get the size of string
n1 = len(s1)
n2 = len(s2)
ans = task.lcs(s1, s2, n1, n2, 0, 0)
#  Display length of common substring
print("\n ", ans )

if __name__ == "__main__": main()``````

#### Output

``  4``
``````#   Ruby Program for
#   Longest common subsequence

class LongestSubsequence
#  Returns the max value of given two numbers
def maxValue(a, b)
if (a > b)
return a
else
return b
end

end

#  Returns the length of common substring
def lcs(s1, s2, n1, n2, i, j)
if (i == n1 || j == n2)
#  When string length exceeds
return 0
elsif(s1[i] == s2[j])
#  When similar characters meet
return 1 + self.lcs(s1, s2, n1, n2, i + 1, j + 1)
else
#  Through recursively find similar characters
return self.maxValue(self.lcs(s1, s2, n1, n2, i + 1, j), self.lcs(s1, s2, n1, n2, i, j + 1))
end

end

end

def main()
s1 = "AABCAEGDS"
#  Get the size of string
n1 = s1.length()
n2 = s2.length()
ans = task.lcs(s1, s2, n1, n2, 0, 0)
#  Display length of common substring
print("\n ", ans ,"\n")
end

main()``````

#### Output

`````` 4
``````
``````/*
Scala Program for
Longest common subsequence
*/
class LongestSubsequence
{
// Returns the max value of given two numbers
def maxValue(a: Int, b: Int): Int = {
if (a > b)
{
return a;
}
else
{
return b;
}
}
// Returns the length of common substring
def lcs(s1: String, s2: String, n1: Int, n2: Int, i: Int, j: Int): Int = {
if (i == n1 || j == n2)
{
// When string length exceeds
return 0;
}
else if (s1(i) == s2(j))
{
// When similar characters meet
return 1 + this.lcs(s1, s2, n1, n2, i + 1, j + 1);
}
else
{
// Through recursively find similar characters
return this.maxValue(this.lcs(s1, s2, n1, n2, i + 1, j), this.lcs(s1, s2, n1, n2, i, j + 1));
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: LongestSubsequence = new LongestSubsequence();
var s1: String = "AABCAEGDS";
// Get the size of string
var n1: Int = s1.length();
var n2: Int = s2.length();
var ans: Int = task.lcs(s1, s2, n1, n2, 0, 0);
// Display length of common substring
print("\n " + ans + "\n");
}
}``````

#### Output

`` 4``
``````/*
Swift 4 Program for
Longest common subsequence
*/
class LongestSubsequence
{
// Returns the max value of given two numbers
func maxValue(_ a: Int, _ b: Int)->Int
{
if (a > b)
{
return a;
}
else
{
return b;
}
}
// Returns the length of common substring
func lcs(_ s1: String, _ s2: String, _ n1: Int, _ n2: Int, _ i: Int, _ j: Int)->Int
{
if (i == n1 || j == n2)
{
// When string length exceeds
return 0;
}
else if (Array(s1)[i] == Array(s2)[j])
{
// When similar characters meet
return 1 + self.lcs(s1, s2, n1, n2, i + 1, j + 1);
}
else
{
// Through recursively find similar characters
return self.maxValue(self.lcs(s1, s2, n1, n2, i + 1, j), self.lcs(s1, s2, n1, n2, i, j + 1));
}
}
}
func main()
{
let s1: String = "AABCAEGDS";
// Get the size of string
let n1: Int = s1.count;
let n2: Int = s2.count;
let ans: Int = task.lcs(s1, s2, n1, n2, 0, 0);
// Display length of common substring
print("\n ", ans );
}
main();``````

#### Output

``  4``
``````/*
Kotlin Program for
Longest common subsequence
*/
class LongestSubsequence
{
// Returns the max value of given two numbers
fun maxValue(a: Int, b: Int): Int
{
if (a > b)
{
return a;
}
else
{
return b;
}
}
// Returns the length of common substring
fun lcs(s1: String, s2: String, n1: Int, n2: Int, i: Int, j: Int): Int
{
if (i == n1 || j == n2)
{
// When string length exceeds
return 0;
}
else if (s1[i] == s2[j])
{
// When similar characters meet
return 1 + this.lcs(s1, s2, n1, n2, i + 1, j + 1);
}
else
{
// Through recursively find similar characters
return this.maxValue(this.lcs(s1, s2, n1, n2, i + 1, j), this.lcs(s1, s2, n1, n2, i, j + 1));
}
}
}
fun main(args: Array < String > ): Unit
{
var s1: String = "AABCAEGDS";
// Get the size of string
var n1: Int = s1.count();
var n2: Int = s2.count();
var ans: Int = task.lcs(s1, s2, n1, n2, 0, 0);
// Display length of common substring
print("\n " + ans + "\n");
}``````

#### Output

`` 4``

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

Categories
Relative Post