# Longest common subsequence

Here given code implementation process.

```
// 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";
const char *s2 = "ADBSEDF";
// 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)
{
LongestSubsequence task = new LongestSubsequence();
String s1 = "AABCAEGDS";
String s2 = "ADBSEDF";
// 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()
{
LongestSubsequence task = LongestSubsequence();
string s1 = "AABCAEGDS";
string s2 = "ADBSEDF";
// 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)
{
LongestSubsequence task = new LongestSubsequence();
String s1 = "AABCAEGDS";
String s2 = "ADBSEDF";
// 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()
{
$task = new LongestSubsequence();
$s1 = "AABCAEGDS";
$s2 = "ADBSEDF";
// 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 task = new LongestSubsequence();
var s1 = "AABCAEGDS";
var s2 = "ADBSEDF";
// 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() :
task = LongestSubsequence()
s1 = "AABCAEGDS"
s2 = "ADBSEDF"
# 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()
task = LongestSubsequence.new()
s1 = "AABCAEGDS"
s2 = "ADBSEDF"
# 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";
var s2: String = "ADBSEDF";
// 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 task: LongestSubsequence = LongestSubsequence();
let s1: String = "AABCAEGDS";
let s2: String = "ADBSEDF";
// 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 task: LongestSubsequence = LongestSubsequence();
var s1: String = "AABCAEGDS";
var s2: String = "ADBSEDF";
// 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`

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.

## New Comment