Print Longest common subsequence
Here given code implementation process.
/*
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
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