Shortest Common Supersequence
Here given code implementation process.
/*
Java program for
Shortest Common Supersequence
*/
public class Supersequence
{
// Returns minimum of given values
public int minValue(int x, int y)
{
if (x < y)
{
return x;
}
return y;
}
// Find length of shortest common Supersequence
public void lengthSCS(String a, String b)
{
int n = a.length();
int m = b.length();
// Auxiliary space
int[][] dp = new int[n + 1][m + 1];
// Outer loop, executing this from 0 to n (length of a)
for (int i = 0; i <= n; ++i)
{
// Inner loop, executing this from 0 to m (length of b)
for (int j = 0; j <= m; ++j)
{
if (i == 0)
{
// When i is zero
dp[i][j] = j;
}
else if (j == 0)
{
// When j is zero
dp[i][j] = i;
}
else if (a.charAt(i - 1) == b.charAt(j - 1))
{
// When character of i-1 and j-1 position are same
dp[i][j] = dp[i - 1][j - 1] + 1;
}
else
{
// When character of i-1 and j-1 position are not same
dp[i][j] = minValue(dp[i][j - 1], dp[i - 1][j]) + 1;
}
}
}
// Display given strings
System.out.println(" Given string a : " + a);
System.out.println(" Given string b : " + b);
// Display calculated result
System.out.println(" Result : " + dp[n][m]);
}
public static void main(String[] args)
{
Supersequence task = new Supersequence();
// Test A
// String a : abc
// String b : fab
// [fabc] Supersequence
// Result = 4
task.lengthSCS("abc", "fab");
// Test B
// String a : project
// String b : objects
// [probjects]
// Result : 9
task.lengthSCS("project", "objects");
// Test C
// String a : match
// String b : attack
// [mattachk,matatchk,mattackh] etc
// Result : 8 (length of Supersequence)
task.lengthSCS("match", "attack");
// Test D
// String a : abc
// String b : abc
// [abc] etc
// Result : 3
task.lengthSCS("abc", "abc");
}
}
Output
Given string a : abc
Given string b : fab
Result : 4
Given string a : project
Given string b : objects
Result : 9
Given string a : match
Given string b : attack
Result : 8
Given string a : abc
Given string b : abc
Result : 3
// Include header file
#include <iostream>
#include <string>
using namespace std;
/*
C++ program for
Shortest Common Supersequence
*/
class Supersequence
{
public:
// Returns minimum of given values
int minValue(int x, int y)
{
if (x < y)
{
return x;
}
return y;
}
// Find length of shortest common Supersequence
void lengthSCS(string a, string b)
{
int n = a.length();
int m = b.length();
// Auxiliary space
int dp[n + 1][m + 1];
// Outer loop, executing this from 0 to n (length of a)
for (int i = 0; i <= n; ++i)
{
// Inner loop, executing this from 0 to m (length of b)
for (int j = 0; j <= m; ++j)
{
if (i == 0)
{
// When i is zero
dp[i][j] = j;
}
else if (j == 0)
{
// When j is zero
dp[i][j] = i;
}
else if (a[i - 1] == b[j - 1])
{
// When character of i-1 and j-1 position are same
dp[i][j] = dp[i - 1][j - 1] + 1;
}
else
{
// When character of i-1 and j-1 position are not same
dp[i][j] = this->minValue(dp[i][j - 1], dp[i - 1][j]) + 1;
}
}
}
// Display given strings
cout << " Given string a : " << a << endl;
cout << " Given string b : " << b << endl;
// Display calculated result
cout << " Result : " << dp[n][m] << endl;
}
};
int main()
{
Supersequence *task = new Supersequence();
// Test A
// String a : abc
// String b : fab
// [fabc] Supersequence
// Result = 4
task->lengthSCS("abc", "fab");
// Test B
// String a : project
// String b : objects
// [probjects]
// Result : 9
task->lengthSCS("project", "objects");
// Test C
// String a : match
// String b : attack
// [mattachk,matatchk,mattackh] etc
// Result : 8 (length of Supersequence)
task->lengthSCS("match", "attack");
// Test D
// String a : abc
// String b : abc
// [abc] etc
// Result : 3
task->lengthSCS("abc", "abc");
return 0;
}
Output
Given string a : abc
Given string b : fab
Result : 4
Given string a : project
Given string b : objects
Result : 9
Given string a : match
Given string b : attack
Result : 8
Given string a : abc
Given string b : abc
Result : 3
// Include namespace system
using System;
/*
Csharp program for
Shortest Common Supersequence
*/
public class Supersequence
{
// Returns minimum of given values
public int minValue(int x, int y)
{
if (x < y)
{
return x;
}
return y;
}
// Find length of shortest common Supersequence
public void lengthSCS(String a, String b)
{
int n = a.Length;
int m = b.Length;
// Auxiliary space
int[,] dp = new int[n + 1,m + 1];
// Outer loop, executing this from 0 to n (length of a)
for (int i = 0; i <= n; ++i)
{
// Inner loop, executing this from 0 to m (length of b)
for (int j = 0; j <= m; ++j)
{
if (i == 0)
{
// When i is zero
dp[i,j] = j;
}
else if (j == 0)
{
// When j is zero
dp[i,j] = i;
}
else if (a[i - 1] == b[j - 1])
{
// When character of i-1 and j-1 position are same
dp[i,j] = dp[i - 1,j - 1] + 1;
}
else
{
// When character of i-1 and j-1 position are not same
dp[i,j] = this.minValue(dp[i,j - 1], dp[i - 1,j]) + 1;
}
}
}
// Display given strings
Console.WriteLine(" Given string a : " + a);
Console.WriteLine(" Given string b : " + b);
// Display calculated result
Console.WriteLine(" Result : " + dp[n,m]);
}
public static void Main(String[] args)
{
Supersequence task = new Supersequence();
// Test A
// String a : abc
// String b : fab
// [fabc] Supersequence
// Result = 4
task.lengthSCS("abc", "fab");
// Test B
// String a : project
// String b : objects
// [probjects]
// Result : 9
task.lengthSCS("project", "objects");
// Test C
// String a : match
// String b : attack
// [mattachk,matatchk,mattackh] etc
// Result : 8 (length of Supersequence)
task.lengthSCS("match", "attack");
// Test D
// String a : abc
// String b : abc
// [abc] etc
// Result : 3
task.lengthSCS("abc", "abc");
}
}
Output
Given string a : abc
Given string b : fab
Result : 4
Given string a : project
Given string b : objects
Result : 9
Given string a : match
Given string b : attack
Result : 8
Given string a : abc
Given string b : abc
Result : 3
package main
import "fmt"
/*
Go program for
Shortest Common Supersequence
*/
// Returns minimum of given values
func minValue(x, y int) int {
if x < y {
return x
}
return y
}
// Find length of shortest common Supersequence
func lengthSCS(a, b string) {
var n int = len(a)
var m int = len(b)
// Auxiliary space
var dp = make([][] int, n + 1)
for i := 0; i < n + 1; i++ {
dp[i] = make([]int,m+1)
}
// Outer loop, executing this from 0 to n (length of a)
for i := 0 ; i <= n ; i++ {
// Inner loop, executing this from 0 to m (length of b)
for j := 0 ; j <= m ; j++ {
if i == 0 {
// When i is zero
dp[i][j] = j
} else if j == 0 {
// When j is zero
dp[i][j] = i
} else if a[i - 1] == b[j - 1] {
// When character of i-1 and j-1 position are same
dp[i][j] = dp[i - 1][j - 1] + 1
} else {
// When character of i-1 and j-1 position are not same
dp[i][j] = minValue(dp[i][j - 1], dp[i - 1][j]) + 1
}
}
}
// Display given strings
fmt.Println(" Given string a : ", a)
fmt.Println(" Given string b : ", b)
// Display calculated result
fmt.Println(" Result : ", dp[n][m])
}
func main() {
// Test A
// String a : abc
// String b : fab
// [fabc] Supersequence
// Result = 4
lengthSCS("abc", "fab")
// Test B
// String a : project
// String b : objects
// [probjects]
// Result : 9
lengthSCS("project", "objects")
// Test C
// String a : match
// String b : attack
// [mattachk,matatchk,mattackh] etc
// Result : 8 (length of Supersequence)
lengthSCS("match", "attack")
// Test D
// String a : abc
// String b : abc
// [abc] etc
// Result : 3
lengthSCS("abc", "abc")
}
Output
Given string a : abc
Given string b : fab
Result : 4
Given string a : project
Given string b : objects
Result : 9
Given string a : match
Given string b : attack
Result : 8
Given string a : abc
Given string b : abc
Result : 3
<?php
/*
Php program for
Shortest Common Supersequence
*/
class Supersequence
{
// Returns minimum of given values
public function minValue($x, $y)
{
if ($x < $y)
{
return $x;
}
return $y;
}
// Find length of shortest common Supersequence
public function lengthSCS($a, $b)
{
$n = strlen($a);
$m = strlen($b);
// Auxiliary space
$dp = array_fill(0, $n + 1, array_fill(0, $m + 1, 0));
// Outer loop, executing this from 0 to n (length of a)
for ($i = 0; $i <= $n; ++$i)
{
// Inner loop, executing this from 0 to m (length of b)
for ($j = 0; $j <= $m; ++$j)
{
if ($i == 0)
{
// When i is zero
$dp[$i][$j] = $j;
}
else if ($j == 0)
{
// When j is zero
$dp[$i][$j] = $i;
}
else if ($a[$i - 1] == $b[$j - 1])
{
// When character of i-1 and j-1 position are same
$dp[$i][$j] = $dp[$i - 1][$j - 1] + 1;
}
else
{
// When character of i-1 and j-1 position are not same
$dp[$i][$j] = $this->minValue($dp[$i][$j - 1], $dp[$i - 1][$j]) + 1;
}
}
}
// Display given strings
echo(" Given string a : ".$a.
"\n");
echo(" Given string b : ".$b.
"\n");
// Display calculated result
echo(" Result : ".$dp[$n][$m].
"\n");
}
}
function main()
{
$task = new Supersequence();
// Test A
// String a : abc
// String b : fab
// [fabc] Supersequence
// Result = 4
$task->lengthSCS("abc", "fab");
// Test B
// String a : project
// String b : objects
// [probjects]
// Result : 9
$task->lengthSCS("project", "objects");
// Test C
// String a : match
// String b : attack
// [mattachk,matatchk,mattackh] etc
// Result : 8 (length of Supersequence)
$task->lengthSCS("match", "attack");
// Test D
// String a : abc
// String b : abc
// [abc] etc
// Result : 3
$task->lengthSCS("abc", "abc");
}
main();
Output
Given string a : abc
Given string b : fab
Result : 4
Given string a : project
Given string b : objects
Result : 9
Given string a : match
Given string b : attack
Result : 8
Given string a : abc
Given string b : abc
Result : 3
/*
Node JS program for
Shortest Common Supersequence
*/
class Supersequence
{
// Returns minimum of given values
minValue(x, y)
{
if (x < y)
{
return x;
}
return y;
}
// Find length of shortest common Supersequence
lengthSCS(a, b)
{
var n = a.length;
var m = b.length;
// Auxiliary space
var dp = Array(n + 1).fill(0).map(() => new Array(m + 1).fill(0));
// Outer loop, executing this from 0 to n (length of a)
for (var i = 0; i <= n; ++i)
{
// Inner loop, executing this from 0 to m (length of b)
for (var j = 0; j <= m; ++j)
{
if (i == 0)
{
// When i is zero
dp[i][j] = j;
}
else if (j == 0)
{
// When j is zero
dp[i][j] = i;
}
else if (a.charAt(i - 1) == b.charAt(j - 1))
{
// When character of i-1 and j-1 position are same
dp[i][j] = dp[i - 1][j - 1] + 1;
}
else
{
// When character of i-1 and j-1 position are not same
dp[i][j] = this.minValue(dp[i][j - 1], dp[i - 1][j]) + 1;
}
}
}
// Display given strings
console.log(" Given string a : " + a);
console.log(" Given string b : " + b);
// Display calculated result
console.log(" Result : " + dp[n][m]);
}
}
function main()
{
var task = new Supersequence();
// Test A
// String a : abc
// String b : fab
// [fabc] Supersequence
// Result = 4
task.lengthSCS("abc", "fab");
// Test B
// String a : project
// String b : objects
// [probjects]
// Result : 9
task.lengthSCS("project", "objects");
// Test C
// String a : match
// String b : attack
// [mattachk,matatchk,mattackh] etc
// Result : 8 (length of Supersequence)
task.lengthSCS("match", "attack");
// Test D
// String a : abc
// String b : abc
// [abc] etc
// Result : 3
task.lengthSCS("abc", "abc");
}
main();
Output
Given string a : abc
Given string b : fab
Result : 4
Given string a : project
Given string b : objects
Result : 9
Given string a : match
Given string b : attack
Result : 8
Given string a : abc
Given string b : abc
Result : 3
# Python 3 program for
# Shortest Common Supersequence
class Supersequence :
# Returns minimum of given values
def minValue(self, x, y) :
if (x < y) :
return x
return y
# Find length of shortest common Supersequence
def lengthSCS(self, a, b) :
n = len(a)
m = len(b)
# Auxiliary space
dp = [[0] * (m + 1) for _ in range(n + 1) ]
i = 0
# Outer loop, executing this from 0 to n (length of a)
while (i <= n) :
j = 0
# Inner loop, executing this from 0 to m (length of b)
while (j <= m) :
if (i == 0) :
# When i is zero
dp[i][j] = j
elif (j == 0) :
# When j is zero
dp[i][j] = i
elif (a[i - 1] == b[j - 1]) :
# When character of i-1 and j-1 position are same
dp[i][j] = dp[i - 1][j - 1] + 1
else :
# When character of i-1 and j-1 position are not same
dp[i][j] = self.minValue(dp[i][j - 1], dp[i - 1][j]) + 1
j += 1
i += 1
# Display given strings
print(" Given string a : ", a)
print(" Given string b : ", b)
# Display calculated result
print(" Result : ", dp[n][m])
def main() :
task = Supersequence()
# Test A
# String a : abc
# String b : fab
# [fabc] Supersequence
# Result = 4
task.lengthSCS("abc", "fab")
# Test B
# String a : project
# String b : objects
# [probjects]
# Result : 9
task.lengthSCS("project", "objects")
# Test C
# String a : match
# String b : attack
# [mattachk,matatchk,mattackh] etc
# Result : 8 (length of Supersequence)
task.lengthSCS("match", "attack")
# Test D
# String a : abc
# String b : abc
# [abc] etc
# Result : 3
task.lengthSCS("abc", "abc")
if __name__ == "__main__": main()
Output
Given string a : abc
Given string b : fab
Result : 4
Given string a : project
Given string b : objects
Result : 9
Given string a : match
Given string b : attack
Result : 8
Given string a : abc
Given string b : abc
Result : 3
# Ruby program for
# Shortest Common Supersequence
class Supersequence
# Returns minimum of given values
def minValue(x, y)
if (x < y)
return x
end
return y
end
# Find length of shortest common Supersequence
def lengthSCS(a, b)
n = a.length
m = b.length
# Auxiliary space
dp = Array.new(n + 1) {Array.new(m + 1) {0}}
i = 0
# Outer loop, executing this from 0 to n (length of a)
while (i <= n)
j = 0
# Inner loop, executing this from 0 to m (length of b)
while (j <= m)
if (i == 0)
# When i is zero
dp[i][j] = j
elsif (j == 0)
# When j is zero
dp[i][j] = i
elsif (a[i - 1] == b[j - 1])
# When character of i-1 and j-1 position are same
dp[i][j] = dp[i - 1][j - 1] + 1
else
# When character of i-1 and j-1 position are not same
dp[i][j] = self.minValue(dp[i][j - 1], dp[i - 1][j]) + 1
end
j += 1
end
i += 1
end
# Display given strings
print(" Given string a : ", a, "\n")
print(" Given string b : ", b, "\n")
# Display calculated result
print(" Result : ", dp[n][m], "\n")
end
end
def main()
task = Supersequence.new()
# Test A
# String a : abc
# String b : fab
# [fabc] Supersequence
# Result = 4
task.lengthSCS("abc", "fab")
# Test B
# String a : project
# String b : objects
# [probjects]
# Result : 9
task.lengthSCS("project", "objects")
# Test C
# String a : match
# String b : attack
# [mattachk,matatchk,mattackh] etc
# Result : 8 (length of Supersequence)
task.lengthSCS("match", "attack")
# Test D
# String a : abc
# String b : abc
# [abc] etc
# Result : 3
task.lengthSCS("abc", "abc")
end
main()
Output
Given string a : abc
Given string b : fab
Result : 4
Given string a : project
Given string b : objects
Result : 9
Given string a : match
Given string b : attack
Result : 8
Given string a : abc
Given string b : abc
Result : 3
import scala.collection.mutable._;
/*
Scala program for
Shortest Common Supersequence
*/
class Supersequence()
{
// Returns minimum of given values
def minValue(x: Int, y: Int): Int = {
if (x < y)
{
return x;
}
return y;
}
// Find length of shortest common Supersequence
def lengthSCS(a: String, b: String): Unit = {
var n: Int = a.length();
var m: Int = b.length();
// Auxiliary space
var dp: Array[Array[Int]] = Array.fill[Int](n + 1, m + 1)(0);
var i: Int = 0;
// Outer loop, executing this from 0 to n (length of a)
while (i <= n)
{
var j: Int = 0;
// Inner loop, executing this from 0 to m (length of b)
while (j <= m)
{
if (i == 0)
{
// When i is zero
dp(i)(j) = j;
}
else if (j == 0)
{
// When j is zero
dp(i)(j) = i;
}
else if (a.charAt(i - 1) == b.charAt(j - 1))
{
// When character of i-1 and j-1 position are same
dp(i)(j) = dp(i - 1)(j - 1) + 1;
}
else
{
// When character of i-1 and j-1 position are not same
dp(i)(j) = minValue(dp(i)(j - 1), dp(i - 1)(j)) + 1;
}
j += 1;
}
i += 1;
}
// Display given strings
println(" Given string a : " + a);
println(" Given string b : " + b);
// Display calculated result
println(" Result : " + dp(n)(m));
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: Supersequence = new Supersequence();
// Test A
// String a : abc
// String b : fab
// [fabc] Supersequence
// Result = 4
task.lengthSCS("abc", "fab");
// Test B
// String a : project
// String b : objects
// [probjects]
// Result : 9
task.lengthSCS("project", "objects");
// Test C
// String a : match
// String b : attack
// [mattachk,matatchk,mattackh] etc
// Result : 8 (length of Supersequence)
task.lengthSCS("match", "attack");
// Test D
// String a : abc
// String b : abc
// [abc] etc
// Result : 3
task.lengthSCS("abc", "abc");
}
}
Output
Given string a : abc
Given string b : fab
Result : 4
Given string a : project
Given string b : objects
Result : 9
Given string a : match
Given string b : attack
Result : 8
Given string a : abc
Given string b : abc
Result : 3
import Foundation;
/*
Swift 4 program for
Shortest Common Supersequence
*/
class Supersequence
{
// Returns minimum of given values
func minValue(_ x: Int, _ y: Int) -> Int
{
if (x < y)
{
return x;
}
return y;
}
// Find length of shortest common Supersequence
func lengthSCS(_ a1: String, _ b1: String)
{
let a = Array(a1);
let b = Array(b1);
let n: Int = a.count;
let m: Int = b.count;
// Auxiliary space
var dp: [
[Int]
] = Array(repeating: Array(repeating: 0, count: m + 1), count: n + 1);
var i: Int = 0;
// Outer loop, executing this from 0 to n (length of a)
while (i <= n)
{
var j: Int = 0;
// Inner loop, executing this from 0 to m (length of b)
while (j <= m)
{
if (i == 0)
{
// When i is zero
dp[i][j] = j;
}
else if (j == 0)
{
// When j is zero
dp[i][j] = i;
}
else if (a[i - 1] == b[j - 1])
{
// When character of i-1 and j-1 position are same
dp[i][j] = dp[i - 1][j - 1] + 1;
}
else
{
// When character of i-1 and j-1 position are not same
dp[i][j] = self.minValue(dp[i][j - 1], dp[i - 1][j]) + 1;
}
j += 1;
}
i += 1;
}
// Display given strings
print(" Given string a : ", a1);
print(" Given string b : ", b1);
// Display calculated result
print(" Result : ", dp[n][m]);
}
}
func main()
{
let task: Supersequence = Supersequence();
// Test A
// String a : abc
// String b : fab
// [fabc] Supersequence
// Result = 4
task.lengthSCS("abc", "fab");
// Test B
// String a : project
// String b : objects
// [probjects]
// Result : 9
task.lengthSCS("project", "objects");
// Test C
// String a : match
// String b : attack
// [mattachk,matatchk,mattackh] etc
// Result : 8 (length of Supersequence)
task.lengthSCS("match", "attack");
// Test D
// String a : abc
// String b : abc
// [abc] etc
// Result : 3
task.lengthSCS("abc", "abc");
}
main();
Output
Given string a : abc
Given string b : fab
Result : 4
Given string a : project
Given string b : objects
Result : 9
Given string a : match
Given string b : attack
Result : 8
Given string a : abc
Given string b : abc
Result : 3
/*
Kotlin program for
Shortest Common Supersequence
*/
class Supersequence
{
// Returns minimum of given values
fun minValue(x: Int, y: Int): Int
{
if (x < y)
{
return x;
}
return y;
}
// Find length of shortest common Supersequence
fun lengthSCS(a: String, b: String): Unit
{
val n: Int = a.length;
val m: Int = b.length;
// Auxiliary space
val dp: Array < Array < Int >> = Array(n + 1)
{
Array(m + 1)
{
0
}
};
var i: Int = 0;
// Outer loop, executing this from 0 to n (length of a)
while (i <= n)
{
var j: Int = 0;
// Inner loop, executing this from 0 to m (length of b)
while (j <= m)
{
if (i == 0)
{
// When i is zero
dp[i][j] = j;
}
else if (j == 0)
{
// When j is zero
dp[i][j] = i;
}
else if (a.get(i - 1) == b.get(j - 1))
{
// When character of i-1 and j-1 position are same
dp[i][j] = dp[i - 1][j - 1] + 1;
}
else
{
// When character of i-1 and j-1 position are not same
dp[i][j] = this.minValue(dp[i][j - 1], dp[i - 1][j]) + 1;
}
j += 1;
}
i += 1;
}
// Display given strings
println(" Given string a : " + a);
println(" Given string b : " + b);
// Display calculated result
println(" Result : " + dp[n][m]);
}
}
fun main(args: Array < String > ): Unit
{
val task: Supersequence = Supersequence();
// Test A
// String a : abc
// String b : fab
// [fabc] Supersequence
// Result = 4
task.lengthSCS("abc", "fab");
// Test B
// String a : project
// String b : objects
// [probjects]
// Result : 9
task.lengthSCS("project", "objects");
// Test C
// String a : match
// String b : attack
// [mattachk,matatchk,mattackh] etc
// Result : 8 (length of Supersequence)
task.lengthSCS("match", "attack");
// Test D
// String a : abc
// String b : abc
// [abc] etc
// Result : 3
task.lengthSCS("abc", "abc");
}
Output
Given string a : abc
Given string b : fab
Result : 4
Given string a : project
Given string b : objects
Result : 9
Given string a : match
Given string b : attack
Result : 8
Given string a : abc
Given string b : abc
Result : 3
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