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] = 0
for j = 0 to n:
dp[0][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:
- The given texts are "adsafbsasc" and "hagvswebrca".
- The algorithm uses dynamic programming to find the LCS between the texts.
- 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. - The algorithm iterates through the characters of the texts and fills the
dp
array according to the LCS logic. - After filling the
dp
array, the length of the LCS is obtained fromdp[m][n]
. - A character array,
result
, is created to store the LCS. - Using the
dp
array, the algorithm traces back and constructs the LCS character by character. - The resulting LCS is stored in the
result
array. - 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 *text1 = "adsafbsasc";
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)
{
LCP task = new LCP();
String text1 = "adsafbsasc";
String text2 = "hagvswebrca";
task.printLCP(text1, text2);
}
}
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()
{
LCP *task = new LCP();
string text1 = "adsafbsasc";
string text2 = "hagvswebrca";
task->printLCP(text1, text2);
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)
{
LCP task = new LCP();
String text1 = "adsafbsasc";
String text2 = "hagvswebrca";
task.printLCP(text1, text2);
}
}
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 text1 string = "adsafbsasc"
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()
{
$task = new LCP();
$text1 = "adsafbsasc";
$text2 = "hagvswebrca";
$task->printLCP($text1, $text2);
}
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 task = new LCP();
var text1 = "adsafbsasc";
var text2 = "hagvswebrca";
task.printLCP(text1, text2);
}
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 = [[0] * (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() :
task = LCP()
text1 = "adsafbsasc"
text2 = "hagvswebrca"
task.printLCP(text1, text2)
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()
task = LCP.new()
text1 = "adsafbsasc"
text2 = "hagvswebrca"
task.printLCP(text1, text2)
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 text1: String = "adsafbsasc";
var text2: String = "hagvswebrca";
task.printLCP(text1, text2);
}
}
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 task: LCP = LCP();
let text1: String = "adsafbsasc";
let text2: String = "hagvswebrca";
task.printLCP(text1, text2);
}
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 task: LCP = LCP();
val text1: String = "adsafbsasc";
val text2: String = "hagvswebrca";
task.printLCP(text1, text2);
}
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)
.
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