Posted on by Kalkicode
Code Dynamic Programming

# Print Longest common subsequence

In this article, we will discuss the problem of finding and printing the Longest Common Subsequence (LCS) between two given strings. The Longest Common Subsequence is the longest sequence of characters that appears in the same order in both strings.

## Problem Statement

The problem is as follows: given two strings, we want to find the longest subsequence that is common to both strings and print it.

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. For example, consider the strings "ABCD" and "ACDF". The longest common subsequence between them is "ACD".

## Pseudocode Algorithm

Let's understand the algorithm to solve this problem:

``````
printLCP(text1, text2):
// Get the length of text1 and text2
m = length(text1)
n = length(text2)

// Create a 2D array to store the dynamic programming values
dp[m+1][n+1]

// Initialize the first row and first column with zeros
for i = 0 to m:
dp[i] = 0
for j = 0 to n:
dp[j] = 0

// Fill the dynamic programming table
for i = 1 to m:
for j = 1 to n:
if text1[i-1] == text2[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])

// Find the length of the LCS
length = dp[m][n]

// Create a character array to store the LCS
result[length+1]

// Trace back to find the LCS
k = m
l = n
while k > 0 and l > 0:
if text1[k-1] == text2[l-1]:
length--
k--
l--
result[length] = text1[k]
else if dp[k-1][l] > dp[k][l-1]:
k--
else:
l--

// Print the given texts and the result
print "Given text1:", text1
print "Given text2:", text2
print "Result:", result
``````

## Explanation

Let's go through the explanation of the code and the resulting output step by step:

1. The given texts are "adsafbsasc" and "hagvswebrca".
2. The algorithm uses dynamic programming to find the LCS between the texts.
3. A 2D array, `dp`, is initialized to store the dynamic programming values. The size of the array is determined by the lengths of the texts.
4. The algorithm iterates through the characters of the texts and fills the `dp` array according to the LCS logic.
5. After filling the `dp` array, the length of the LCS is obtained from `dp[m][n]`.
6. A character array, `result`, is created to store the LCS.
7. Using the `dp` array, the algorithm traces back and constructs the LCS character by character.
8. The resulting LCS is stored in the `result` array.
9. Finally, the given texts and the resulting LCS are printed.

## Resultant Output Explanation

The given texts are:

``````Given text1: adsafbsasc
Given text2: hagvswebrca``````

The longest common subsequence (LCS) between the given texts is:

``Result: asbc``

## Code Solution

``````/*
C program for
Print Longest common subsequence
*/
#include <stdio.h>
#include <string.h>

int maxValue(int a, int b)
{
if (a > b)
{
return a;
}
return b;
}
void printLCP(char *text1, char *text2)
{
// Get the length of text1 and text2
int m = strlen(text1);
int n = strlen(text2);

int dp[m + 1][n + 1];
// Execute loop through by size of m
for (int i = 0; i <= m; i++)
{
// Execute loop through by size of n
for (int j = 0; j <= n; j++)
{
if (i == 0 || j == 0)
{
// Set first row and first column value is zero
dp[i][j] = 0;
}
else if (text1[i - 1] == text2[j - 1])
{
// When i-1 and j-1 is character are same
dp[i][j] = dp[i - 1][j - 1] + 1;
}
else
{
// Get max value
dp[i][j] = maxValue(dp[i - 1][j], dp[i][j - 1]);
}
}
}

// Find the length of longest common subsequence
int length = dp[m][n];
// Use to collect result
char result[length + 1];
// Set terminate character at the end
result[length] = '\0';

int k = m;
int l = n;
while (k > 0 && l > 0)
{
if (text1[k - 1] == text2[l - 1])
{
length--;
k--;
l--;
result[length] = text1[k];

}
else if (dp[k - 1][l] > dp[k][l - 1])
{
k--;
}
else
{
l--;
}
}
printf("\n Given text1 : %s",text1);
printf("\n Given text2 : %s",text2);
// Display LCS
printf("\n Result : %s", result);
}
int main(int argc, char const *argv[])
{
char *text2 = "hagvswebrca";
printLCP(text1, text2);
return 0;
}``````

#### Output

`````` Given text1 : adsafbsasc
Given text2 : hagvswebrca
Result : asbc``````
``````/*
Java program for
Print Longest common subsequence
*/
public class LCP
{
public int maxValue(int a, int b)
{
if (a > b)
{
return a;
}
return b;
}
public void printLCP(String text1, String text2)
{
// Get the length of text1 and text2
int m = text1.length();
int n = text2.length();
int[][] dp = new int[m + 1][n + 1];
// Execute loop through by size of m
for (int i = 0; i <= m; i++)
{
// Execute loop through by size of n
for (int j = 0; j <= n; j++)
{
if (i == 0 || j == 0)
{
// Set first row and first column value is zero
dp[i][j] = 0;
}
else if (text1.charAt(i - 1) == text2.charAt(j - 1))
{
// When i-1 and j-1 is character are same
dp[i][j] = dp[i - 1][j - 1] + 1;
}
else
{
// Get max value
dp[i][j] = maxValue(dp[i - 1][j], dp[i][j - 1]);
}
}
}
// Use to collect result
String result = "";
int k = m;
int l = n;
while (k > 0 && l > 0)
{
if (text1.charAt(k-1) == text2.charAt(l-1))
{

k--;
l--;
result = text1.charAt(k) + result;
}
else if (dp[k - 1][l] > dp[k][l - 1])
{
k--;
}
else
{
l--;
}
}
System.out.print("\n Given text1 : " + text1);
System.out.print("\n Given text2 : " + text2);
// Display LCS
System.out.print("\n Result : " + result);
}
public static void main(String[] args)
{
String text2 = "hagvswebrca";
}
}``````

#### Output

`````` Given text1 : adsafbsasc
Given text2 : hagvswebrca
Result : asbc``````
``````// Include header file
#include <iostream>
#include <string>

using namespace std;
/*
C++ program for
Print Longest common subsequence
*/
class LCP
{
public: int maxValue(int a, int b)
{
if (a > b)
{
return a;
}
return b;
}
void printLCP(string text1, string text2)
{
// Get the length of text1 and text2
int m = text1.length();
int n = text2.length();
int dp[m + 1][n + 1];
// Execute loop through by size of m
for (int i = 0; i <= m; i++)
{
// Execute loop through by size of n
for (int j = 0; j <= n; j++)
{
if (i == 0 || j == 0)
{
// Set first row and first column value is zero
dp[i][j] = 0;
}
else if (text1[i - 1] == text2[j - 1])
{
// When i-1 and j-1 is character are same
dp[i][j] = dp[i - 1][j - 1] + 1;
}
else
{
// Get max value
dp[i][j] = this->maxValue(dp[i - 1][j], dp[i][j - 1]);
}
}
}
// Use to collect result
string result = "";
int k = m;
int l = n;
while (k > 0 && l > 0)
{
if (text1[k - 1] == text2[l - 1])
{
k--;
l--;
result = (text1[k])  +  result;
}
else if (dp[k - 1][l] > dp[k][l - 1])
{
k--;
}
else
{
l--;
}
}
cout << "\n Given text1 : " << text1;
cout << "\n Given text2 : " << text2;
// Display LCS
cout << "\n Result : " << result;
}
};
int main()
{
string text2 = "hagvswebrca";
return 0;
}``````

#### Output

`````` Given text1 : adsafbsasc
Given text2 : hagvswebrca
Result : asbc``````
``````// Include namespace system
using System;
/*
Csharp program for
Print Longest common subsequence
*/
public class LCP
{
public int maxValue(int a, int b)
{
if (a > b)
{
return a;
}
return b;
}
public void printLCP(String text1, String text2)
{
// Get the length of text1 and text2
int m = text1.Length;
int n = text2.Length;
int[,] dp = new int[m + 1,n + 1];
// Execute loop through by size of m
for (int i = 0; i <= m; i++)
{
// Execute loop through by size of n
for (int j = 0; j <= n; j++)
{
if (i == 0 || j == 0)
{
// Set first row and first column value is zero
dp[i,j] = 0;
}
else if (text1[i - 1] == text2[j - 1])
{
// When i-1 and j-1 is character are same
dp[i,j] = dp[i - 1,j - 1] + 1;
}
else
{
// Get max value
dp[i,j] = this.maxValue(dp[i - 1,j], dp[i,j - 1]);
}
}
}
// Use to collect result
String result = "";
int k = m;
int l = n;
while (k > 0 && l > 0)
{
if (text1[k - 1] == text2[l - 1])
{
k--;
l--;
result = text1[k] + result;
}
else if (dp[k - 1,l] > dp[k,l - 1])
{
k--;
}
else
{
l--;
}
}
Console.Write("\n Given text1 : " + text1);
Console.Write("\n Given text2 : " + text2);
// Display LCS
Console.Write("\n Result : " + result);
}
public static void Main(String[] args)
{
String text2 = "hagvswebrca";
}
}``````

#### Output

`````` Given text1 : adsafbsasc
Given text2 : hagvswebrca
Result : asbc``````
``````package main
import "fmt"
/*
Go program for
Print Longest common subsequence
*/

func maxValue(a, b int) int {
if a > b {
return a
}
return b
}
func printLCP(text1, text2 string) {
// Get the length of text1 and text2
var m int = len(text1)
var n int = len(text2)
var dp = make([][]int,m+1)

for i := 0; i<=m; i++ {
dp[i] = make([]int,n+1)
}
// Execute loop through by size of m
for i := 0 ; i <= m ; i++ {
// Execute loop through by size of n
for j := 0 ; j <= n ; j++ {
if i == 0 || j == 0 {
// Set first row and first column value is zero
dp[i][j] = 0
} else if text1[i - 1] == text2[j - 1] {
// When i-1 and j-1 is character are same
dp[i][j] = dp[i - 1][j - 1] + 1
} else {
// Get max value
dp[i][j] = maxValue(dp[i - 1][j], dp[i][j - 1])
}
}
}
// Use to collect result
var result string = ""
var k int = m
var l int = n
for (k > 0 && l > 0) {
if text1[k - 1] == text2[l - 1] {
k--
l--
result = string(text1[k]) + result
} else if dp[k - 1][l] > dp[k][l - 1] {
k--
} else {
l--
}
}
fmt.Print("\n Given text1 : ", text1)
fmt.Print("\n Given text2 : ", text2)
// Display LCS
fmt.Print("\n Result : ", result)
}
func main() {

var text2 string = "hagvswebrca"
printLCP(text1, text2)
}``````

#### Output

`````` Given text1 : adsafbsasc
Given text2 : hagvswebrca
Result : asbc``````
``````<?php
/*
Php program for
Print Longest common subsequence
*/
class LCP
{
public	function maxValue(\$a, \$b)
{
if (\$a > \$b)
{
return \$a;
}
return \$b;
}
public	function printLCP(\$text1, \$text2)
{
// Get the length of text1 and text2
\$m = strlen(\$text1);
\$n = strlen(\$text2);
\$dp = array_fill(0, \$m + 1, array_fill(0, \$n + 1, 0));
// Execute loop through by size of m
for (\$i = 0; \$i <= \$m; \$i++)
{
// Execute loop through by size of n
for (\$j = 0; \$j <= \$n; \$j++)
{
if (\$i == 0 || \$j == 0)
{
// Set first row and first column value is zero
\$dp[\$i][\$j] = 0;
}
else if (\$text1[\$i - 1] == \$text2[\$j - 1])
{
// When i-1 and j-1 is character are same
\$dp[\$i][\$j] = \$dp[\$i - 1][\$j - 1] + 1;
}
else
{
// Get max value
\$dp[\$i][\$j] = \$this->maxValue(\$dp[\$i - 1][\$j], \$dp[\$i][\$j - 1]);
}
}
}
// Use to collect result
\$result = "";
\$k = \$m;
\$l = \$n;
while (\$k > 0 && \$l > 0)
{
if (\$text1[\$k - 1] == \$text2[\$l - 1])
{
\$k--;
\$l--;
\$result = strval(\$text1[\$k]).\$result;
}
else if (\$dp[\$k - 1][\$l] > \$dp[\$k][\$l - 1])
{
\$k--;
}
else
{
\$l--;
}
}
echo("\n Given text1 : ".\$text1);
echo("\n Given text2 : ".\$text2);
// Display LCS
echo("\n Result : ".\$result);
}
}

function main()
{
\$text2 = "hagvswebrca";
}
main();``````

#### Output

`````` Given text1 : adsafbsasc
Given text2 : hagvswebrca
Result : asbc``````
``````/*
Node JS program for
Print Longest common subsequence
*/
class LCP
{
maxValue(a, b)
{
if (a > b)
{
return a;
}
return b;
}
printLCP(text1, text2)
{
// Get the length of text1 and text2
var m = text1.length;
var n = text2.length;
var dp = Array(m + 1).fill(0).map(() => new Array(n + 1).fill(0));
// Execute loop through by size of m
for (var i = 0; i <= m; i++)
{
// Execute loop through by size of n
for (var j = 0; j <= n; j++)
{
if (i == 0 || j == 0)
{
// Set first row and first column value is zero
dp[i][j] = 0;
}
else if (text1.charAt(i - 1) == text2.charAt(j - 1))
{
// When i-1 and j-1 is character are same
dp[i][j] = dp[i - 1][j - 1] + 1;
}
else
{
// Get max value
dp[i][j] = this.maxValue(dp[i - 1][j], dp[i][j - 1]);
}
}
}
// Use to collect result
var result = "";
var k = m;
var l = n;
while (k > 0 && l > 0)
{
if (text1.charAt(k - 1) == text2.charAt(l - 1))
{
k--;
l--;
result = text1.charAt(k) + result;
}
else if (dp[k - 1][l] > dp[k][l - 1])
{
k--;
}
else
{
l--;
}
}
process.stdout.write("\n Given text1 : " + text1);
process.stdout.write("\n Given text2 : " + text2);
// Display LCS
process.stdout.write("\n Result : " + result);
}
}

function main()
{
var text2 = "hagvswebrca";
}
main();``````

#### Output

`````` Given text1 : adsafbsasc
Given text2 : hagvswebrca
Result : asbc``````
``````#    Python 3 program for
#    Print Longest common subsequence
class LCP :
def maxValue(self, a, b) :
if (a > b) :
return a

return b

def printLCP(self, text1, text2) :
#  Get the length of text1 and text2
m = len(text1)
n = len(text2)
dp = [ * (n + 1) for _ in range(m + 1) ]
i = 0
#  Execute loop through by size of m
while (i <= m) :
j = 0
#  Execute loop through by size of n
while (j <= n) :
if (i == 0 or j == 0) :
#  Set first row and first column value is zero
dp[i][j] = 0
elif (text1[i - 1] == text2[j - 1]) :
#  When i-1 and j-1 is character are same
dp[i][j] = dp[i - 1][j - 1] + 1
else :
#  Get max value
dp[i][j] = self.maxValue(dp[i - 1][j], dp[i][j - 1])

j += 1

i += 1

#  Use to collect result
result = ""
k = m
l = n
while (k > 0 and l > 0) :
if (text1[k - 1] == text2[l - 1]) :
k -= 1
l -= 1
result = str(text1[k]) + result
elif (dp[k - 1][l] > dp[k][l - 1]) :
k -= 1
else :
l -= 1

print("\n Given text1 : ", text1, end = "")
print("\n Given text2 : ", text2, end = "")
#  Display LCS
print("\n Result : ", result, end = "")

def main() :
text2 = "hagvswebrca"

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

#### Output

`````` Given text1 :  adsafbsasc
Given text2 :  hagvswebrca
Result :  asbc``````
``````#    Ruby program for
#    Print Longest common subsequence
class LCP
def maxValue(a, b)
if (a > b)
return a
end

return b
end

def printLCP(text1, text2)
#  Get the length of text1 and text2
m = text1.length
n = text2.length
dp = Array.new(m + 1) {Array.new(n + 1) {0}}
i = 0
#  Execute loop through by size of m
while (i <= m)
j = 0
#  Execute loop through by size of n
while (j <= n)
if (i == 0 || j == 0)
#  Set first row and first column value is zero
dp[i][j] = 0
elsif (text1[i - 1] == text2[j - 1])
#  When i-1 and j-1 is character are same
dp[i][j] = dp[i - 1][j - 1] + 1
else

#  Get max value
dp[i][j] = self.maxValue(dp[i - 1][j], dp[i][j - 1])
end

j += 1
end

i += 1
end

#  Use to collect result
result = ""
k = m
l = n
while (k > 0 && l > 0)
if (text1[k - 1] == text2[l - 1])
k -= 1
l -= 1
result = text1[k].to_s + result
elsif (dp[k - 1][l] > dp[k][l - 1])
k -= 1
else

l -= 1
end

end

print("\n Given text1 : ", text1)
print("\n Given text2 : ", text2)
#  Display LCS
print("\n Result : ", result)
end

end

def main()
text2 = "hagvswebrca"
end

main()``````

#### Output

`````` Given text1 : adsafbsasc
Given text2 : hagvswebrca
Result : asbc``````
``````/*
Scala program for
Print Longest common subsequence
*/
class LCP()
{
def maxValue(a: Int, b: Int): Int = {
if (a > b)
{
return a;
}
return b;
}
def printLCP(text1: String, text2: String): Unit = {
// Get the length of text1 and text2
var m: Int = text1.length();
var n: Int = text2.length();
var dp: Array[Array[Int]] = Array.fill[Int](m + 1, n + 1)(0);
var i: Int = 0;
// Execute loop through by size of m
while (i <= m)
{
var j: Int = 0;
// Execute loop through by size of n
while (j <= n)
{
if (i == 0 || j == 0)
{
// Set first row and first column value is zero
dp(i)(j) = 0;
}
else if (text1.charAt(i - 1) == text2.charAt(j - 1))
{
// When i-1 and j-1 is character are same
dp(i)(j) = dp(i - 1)(j - 1) + 1;
}
else
{
// Get max value
dp(i)(j) = maxValue(dp(i - 1)(j), dp(i)(j - 1));
}
j += 1;
}
i += 1;
}
// Use to collect result
var result: String = "";
var k: Int = m;
var l: Int = n;
while (k > 0 && l > 0)
{
if (text1.charAt(k - 1) == text2.charAt(l - 1))
{
k -= 1;
l -= 1;
result = text1.charAt(k).toString() + result;
}
else if (dp(k - 1)(l) > dp(k)(l - 1))
{
k -= 1;
}
else
{
l -= 1;
}
}
print("\n Given text1 : " + text1);
print("\n Given text2 : " + text2);
// Display LCS
print("\n Result : " + result);
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: LCP = new LCP();
var text2: String = "hagvswebrca";
}
}``````

#### Output

`````` Given text1 : adsafbsasc
Given text2 : hagvswebrca
Result : asbc``````
``````import Foundation;
/*
Swift 4 program for
Print Longest common subsequence
*/
class LCP
{
func maxValue(_ a: Int, _ b: Int) -> Int
{
if (a > b)
{
return a;
}
return b;
}
func printLCP(_ a: String, _ b: String)
{
// Get the length of text1 and text2
let m: Int = a.count;
let n: Int = b.count;
let text1 = Array(a);
let text2 = Array(b);
var dp: [[Int]] =
Array(repeating: Array(repeating: 0, count: n + 1), count: m + 1);
var i: Int = 0;
// Execute loop through by size of m
while (i <= m)
{
var j: Int = 0;
// Execute loop through by size of n
while (j <= n)
{
if (i == 0 || j == 0)
{
// Set first row and first column value is zero
dp[i][j] = 0;
}
else if (text1[i - 1] == text2[j - 1])
{
// When i-1 and j-1 is character are same
dp[i][j] = dp[i - 1][j - 1] + 1;
}
else
{
// Get max value
dp[i][j] = self.maxValue(dp[i - 1][j], dp[i][j - 1]);
}
j += 1;
}
i += 1;
}
// Use to collect result
var result: String = "";
var k: Int = m;
var l: Int = n;
while (k > 0 && l > 0)
{
if (text1[k - 1] == text2[l - 1])
{
k -= 1;
l -= 1;
result = String(text1[k]) + result;
}
else if (dp[k - 1][l] > dp[k][l - 1])
{
k -= 1;
}
else
{
l -= 1;
}
}
print("\n Given text1 : ", a, terminator: "");
print("\n Given text2 : ", b, terminator: "");
// Display LCS
print("\n Result : ", result, terminator: "");
}
}
func main()
{
let text2: String = "hagvswebrca";
}
main();``````

#### Output

`````` Given text1 :  adsafbsasc
Given text2 :  hagvswebrca
Result :  asbc``````
``````/*
Kotlin program for
Print Longest common subsequence
*/
class LCP
{
fun maxValue(a: Int, b: Int): Int
{
if (a > b)
{
return a;
}
return b;
}
fun printLCP(text1: String, text2: String): Unit
{
// Get the length of text1 and text2
val m: Int = text1.length;
val n: Int = text2.length;
var dp: Array < Array < Int >> = Array(m + 1)
{
Array(n + 1)
{
0
}
};
var i: Int = 0;
// Execute loop through by size of m
while (i <= m)
{
var j: Int = 0;
// Execute loop through by size of n
while (j <= n)
{
if (i == 0 || j == 0)
{
// Set first row and first column value is zero
dp[i][j] = 0;
}
else if (text1.get(i - 1) == text2.get(j - 1))
{
// When i-1 and j-1 is character are same
dp[i][j] = dp[i - 1][j - 1] + 1;
}
else
{
// Get max value
dp[i][j] = this.maxValue(dp[i - 1][j], dp[i][j - 1]);
}
j += 1;
}
i += 1;
}
// Use to collect result
var result: String = "";
var k: Int = m;
var l: Int = n;
while (k > 0 && l > 0)
{
if (text1.get(k - 1) == text2.get(l - 1))
{
k -= 1;
l -= 1;
result = text1.get(k).toString() + result;
}
else if (dp[k - 1][l] > dp[k][l - 1])
{
k -= 1;
}
else
{
l -= 1;
}
}
print("\n Given text1 : " + text1);
print("\n Given text2 : " + text2);
// Display LCS
print("\n Result : " + result);
}
}
fun main(args: Array < String > ): Unit
{
val text2: String = "hagvswebrca";
}``````

#### Output

`````` Given text1 : adsafbsasc
Given text2 : hagvswebrca
Result : asbc``````

## Time Complexity

The time complexity of this algorithm is `O(m * n)`, where `m` and `n` are the lengths of the input texts. This is because we iterate through the entire `dp` array of size `(m+1) * (n+1)`.

## 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