Printing Shortest Common Supersequence
The problem is a classic algorithmic challenge that involves finding the shortest string that contains two given strings as subsequences. This problem is relevant in various areas such as DNA sequence alignment, text processing, and computational biology. In this article, we'll delve into the approach to solving the Shortest Common Supersequence problem using dynamic programming and provide a detailed explanation along with code examples.
Problem Statement and Description
Given two strings A and B, the goal of the Shortest Common Supersequence problem is to find the shortest string C that contains both A and B as subsequences. In other words, C should have A and B as subsequences while minimizing its length. The problem finds applications in tasks such as DNA sequence alignment, where researchers want to find the shortest sequence that includes both genetic sequences.
Example
Consider the following examples to grasp the concept:
-
For strings "abc" and "fab": The shortest common supersequence is "fabc", with a length of 4 characters.
-
For strings "project" and "objects": The shortest common supersequence is "probjects", with a length of 9 characters.
-
For strings "match" and "attack": One possible shortest common supersequence is "mattackh", with a length of 8 characters.
-
For strings "abc" and "abc": The shortest common supersequence is simply "abc", as it includes both strings and has a length of 3 characters.
Idea to Solve the Problem
To solve the Shortest Common Supersequence problem, we can utilize dynamic programming. The idea is to build a 2D table where each entry dp[i][j] represents the length of the shortest common supersequence of substrings A[0...i-1] and B[0...j-1].
Standard Pseudocode
function findSCS(a, b):
n = length of string a
m = length of string b
dp = 2D array of size (n+1) x (m+1)
result = empty string
for i from 0 to n:
for j from 0 to m:
if i is 0:
dp[i][j] = j
else if j is 0:
dp[i][j] = i
else if a[i-1] is equal to b[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = minimum of (dp[i][j-1], dp[i-1][j]) + 1
s = n
e = m
while s > 0 and e > 0:
if a[s-1] is equal to b[e-1]:
add a[s-1] to the beginning of result
decrement s and e
else if dp[s-1][e] > dp[s][e-1]:
add b[e-1] to the beginning of result
decrement e
else:
add a[s-1] to the beginning of result
decrement s
while s > 0:
add a[s-1] to the beginning of result
decrement s
while e > 0:
add b[e-1] to the beginning of result
decrement e
print "Given string a :", a
print "Given string b :", b
print "Length :", dp[n][m]
print "Result :", result
Algorithm Explanation
- Initialize a 2D array
dp
of size (n+1) x (m+1) to store the lengths of the shortest common supersequences. - Iterate through the arrays
a
andb
using two nested loops, filling thedp
array based on certain conditions. - Traverse the
dp
array to reconstruct the shortest common supersequence and store it in theresult
variable. - Print the original strings, the length of the shortest common supersequence, and the reconstructed supersequence.
Code Solution
/*
Java program for
Printing 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 findSCS(String a, String b)
{
int n = a.length();
int m = b.length();
String result = "";
// 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);
int min = dp[n][m];
int s = n;
int e = m;
while (s > 0 && e > 0)
{
if (a.charAt(s - 1) == b.charAt(e - 1))
{
// When both string character at position are same from end
result = a.charAt(s - 1) + result;
s--;
e--;
}
else if (dp[s - 1][e] > dp[s][e - 1])
{
result = b.charAt(e - 1) + result;
e--;
}
else
{
result = a.charAt(s - 1) + result;
s--;
}
}
// Collect remaining character of first string
while (s > 0)
{
result = a.charAt(s - 1) + result;
s--;
}
// Collect remaining character of second string
while (e > 0)
{
result = b.charAt(e - 1) + result;
e--;
}
// Display calculated result
System.out.println(" Length : " + dp[n][m]);
System.out.println(" Result : " + result);
}
public static void main(String[] args)
{
Supersequence task = new Supersequence();
// Test A
// String a : abc
// String b : fab
// [fabc] Supersequence
// Result = 4
task.findSCS("abc", "fab");
// Test B
// String a : project
// String b : objects
// [probjects]
// Result : 9
task.findSCS("project", "objects");
// Test C
// String a : match
// String b : attack
// [mattachk,matatchk,mattackh] etc
// Result : 8 (length of Supersequence)
task.findSCS("match", "attack");
// Test D
// String a : abc
// String b : abc
// [abc] etc
// Result : 3
task.findSCS("abc", "abc");
}
}
Output
Given string a : abc
Given string b : fab
Length : 4
Result : fabc
Given string a : project
Given string b : objects
Length : 9
Result : probjects
Given string a : match
Given string b : attack
Length : 8
Result : mattackh
Given string a : abc
Given string b : abc
Length : 3
Result : abc
// Include header file
#include <iostream>
#include <string>
using namespace std;
/*
C++ program for
Printing 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 findSCS(string a, string b)
{
int n = a.length();
int m = b.length();
string result = "";
// 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;
int min = dp[n][m];
int s = n;
int e = m;
while (s > 0 && e > 0)
{
if (a[s - 1] == b[e - 1])
{
// When both string character at position are same from end
result = (a[s - 1]) + result;
s--;
e--;
}
else if (dp[s - 1][e] > dp[s][e - 1])
{
result = (b[e - 1]) + result;
e--;
}
else
{
result = (a[s - 1]) + result;
s--;
}
}
// Collect remaining character of first string
while (s > 0)
{
result = (a[s - 1]) + result;
s--;
}
// Collect remaining character of second string
while (e > 0)
{
result = (b[e - 1]) + result;
e--;
}
// Display calculated result
cout << " Length : " << dp[n][m] << endl;
cout << " Result : " << result << endl;
}
};
int main()
{
Supersequence *task = new Supersequence();
// Test A
// String a : abc
// String b : fab
// [fabc] Supersequence
// Result = 4
task->findSCS("abc", "fab");
// Test B
// String a : project
// String b : objects
// [probjects]
// Result : 9
task->findSCS("project", "objects");
// Test C
// String a : match
// String b : attack
// [mattachk,matatchk,mattackh] etc
// Result : 8 (length of Supersequence)
task->findSCS("match", "attack");
// Test D
// String a : abc
// String b : abc
// [abc] etc
// Result : 3
task->findSCS("abc", "abc");
return 0;
}
Output
Given string a : abc
Given string b : fab
Length : 4
Result : fabc
Given string a : project
Given string b : objects
Length : 9
Result : probjects
Given string a : match
Given string b : attack
Length : 8
Result : mattackh
Given string a : abc
Given string b : abc
Length : 3
Result : abc
// Include namespace system
using System;
/*
Csharp program for
Printing 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 findSCS(String a, String b)
{
int n = a.Length;
int m = b.Length;
String result = "";
// 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);
int min = dp[n,m];
int s = n;
int e = m;
while (s > 0 && e > 0)
{
if (a[s - 1] == b[e - 1])
{
// When both string character at position are same from end
result = a[s - 1] + result;
s--;
e--;
}
else if (dp[s - 1,e] > dp[s,e - 1])
{
result = b[e - 1] + result;
e--;
}
else
{
result = a[s - 1] + result;
s--;
}
}
// Collect remaining character of first string
while (s > 0)
{
result = a[s - 1] + result;
s--;
}
// Collect remaining character of second string
while (e > 0)
{
result = b[e - 1] + result;
e--;
}
// Display calculated result
Console.WriteLine(" Length : " + min);
Console.WriteLine(" Result : " + result);
}
public static void Main(String[] args)
{
Supersequence task = new Supersequence();
// Test A
// String a : abc
// String b : fab
// [fabc] Supersequence
// Result = 4
task.findSCS("abc", "fab");
// Test B
// String a : project
// String b : objects
// [probjects]
// Result : 9
task.findSCS("project", "objects");
// Test C
// String a : match
// String b : attack
// [mattachk,matatchk,mattackh] etc
// Result : 8 (length of Supersequence)
task.findSCS("match", "attack");
// Test D
// String a : abc
// String b : abc
// [abc] etc
// Result : 3
task.findSCS("abc", "abc");
}
}
Output
Given string a : abc
Given string b : fab
Length : 4
Result : fabc
Given string a : project
Given string b : objects
Length : 9
Result : probjects
Given string a : match
Given string b : attack
Length : 8
Result : mattackh
Given string a : abc
Given string b : abc
Length : 3
Result : abc
package main
import "fmt"
/*
Go program for
Printing 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 findSCS(a, b string) {
var n int = len(a)
var m int = len(b)
var result string = ""
// 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)
var min int = dp[n][m]
var s int = n
var e int = m
for (s > 0 && e > 0) {
if a[s - 1] == b[e - 1] {
// When both string character at position are same from end
result = string(a[s - 1]) + result
s--
e--
} else if dp[s - 1][e] > dp[s][e - 1] {
result = string(b[e - 1]) + result
e--
} else {
result = string(a[s - 1]) + result
s--
}
}
// Collect remaining character of first string
for (s > 0) {
result = string(a[s - 1]) + result
s--
}
// Collect remaining character of second string
for (e > 0) {
result = string(b[e - 1]) + result
e--
}
// Display calculated result
fmt.Println(" Length : ", min)
fmt.Println(" Result : ", result)
}
func main() {
// Test A
// String a : abc
// String b : fab
// [fabc] Supersequence
// Result = 4
findSCS("abc", "fab")
// Test B
// String a : project
// String b : objects
// [probjects]
// Result : 9
findSCS("project", "objects")
// Test C
// String a : match
// String b : attack
// [mattachk,matatchk,mattackh] etc
// Result : 8 (length of Supersequence)
findSCS("match", "attack")
// Test D
// String a : abc
// String b : abc
// [abc] etc
// Result : 3
findSCS("abc", "abc")
}
Output
Given string a : abc
Given string b : fab
Length : 4
Result : fabc
Given string a : project
Given string b : objects
Length : 9
Result : probjects
Given string a : match
Given string b : attack
Length : 8
Result : mattackh
Given string a : abc
Given string b : abc
Length : 3
Result : abc
<?php
/*
Php program for
Printing 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 findSCS($a, $b)
{
$n = strlen($a);
$m = strlen($b);
$result = "";
// 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");
$min = $dp[$n][$m];
$s = $n;
$e = $m;
while ($s > 0 && $e > 0)
{
if ($a[$s - 1] == $b[$e - 1])
{
// When both string character at position are same from end
$result = strval($a[$s - 1]).$result;
$s--;
$e--;
}
else if ($dp[$s - 1][$e] > $dp[$s][$e - 1])
{
$result = strval($b[$e - 1]).$result;
$e--;
}
else
{
$result = strval($a[$s - 1]).$result;
$s--;
}
}
// Collect remaining character of first string
while ($s > 0)
{
$result = strval($a[$s - 1]).$result;
$s--;
}
// Collect remaining character of second string
while ($e > 0)
{
$result = strval($b[$e - 1]).$result;
$e--;
}
// Display calculated result
echo(" Length : ".$min."\n");
echo(" Result : ".$result."\n");
}
}
function main()
{
$task = new Supersequence();
// Test A
// String a : abc
// String b : fab
// [fabc] Supersequence
// Result = 4
$task->findSCS("abc", "fab");
// Test B
// String a : project
// String b : objects
// [probjects]
// Result : 9
$task->findSCS("project", "objects");
// Test C
// String a : match
// String b : attack
// [mattachk,matatchk,mattackh] etc
// Result : 8 (length of Supersequence)
$task->findSCS("match", "attack");
// Test D
// String a : abc
// String b : abc
// [abc] etc
// Result : 3
$task->findSCS("abc", "abc");
}
main();
Output
Given string a : abc
Given string b : fab
Length : 4
Result : fabc
Given string a : project
Given string b : objects
Length : 9
Result : probjects
Given string a : match
Given string b : attack
Length : 8
Result : mattackh
Given string a : abc
Given string b : abc
Length : 3
Result : abc
/*
Node JS program for
Printing 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
findSCS(a, b)
{
var n = a.length;
var m = b.length;
var result = "";
// 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);
var min = dp[n][m];
var s = n;
var e = m;
while (s > 0 && e > 0)
{
if (a.charAt(s - 1) == b.charAt(e - 1))
{
// When both string character at position are same from end
result = a.charAt(s - 1) + result;
s--;
e--;
}
else if (dp[s - 1][e] > dp[s][e - 1])
{
result = b.charAt(e - 1) + result;
e--;
}
else
{
result = a.charAt(s - 1) + result;
s--;
}
}
// Collect remaining character of first string
while (s > 0)
{
result = a.charAt(s - 1) + result;
s--;
}
// Collect remaining character of second string
while (e > 0)
{
result = b.charAt(e - 1) + result;
e--;
}
// Display calculated result
console.log(" Length : " + min);
console.log(" Result : " + result);
}
}
function main()
{
var task = new Supersequence();
// Test A
// String a : abc
// String b : fab
// [fabc] Supersequence
// Result = 4
task.findSCS("abc", "fab");
// Test B
// String a : project
// String b : objects
// [probjects]
// Result : 9
task.findSCS("project", "objects");
// Test C
// String a : match
// String b : attack
// [mattachk,matatchk,mattackh] etc
// Result : 8 (length of Supersequence)
task.findSCS("match", "attack");
// Test D
// String a : abc
// String b : abc
// [abc] etc
// Result : 3
task.findSCS("abc", "abc");
}
main();
Output
Given string a : abc
Given string b : fab
Length : 4
Result : fabc
Given string a : project
Given string b : objects
Length : 9
Result : probjects
Given string a : match
Given string b : attack
Length : 8
Result : mattackh
Given string a : abc
Given string b : abc
Length : 3
Result : abc
# Python 3 program for
# Printing 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 findSCS(self, a, b) :
n = len(a)
m = len(b)
result = ""
# 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)
min = dp[n][m]
s = n
e = m
while (s > 0 and e > 0) :
if (a[s - 1] == b[e - 1]) :
# When both string character at position are same from end
result = str(a[s - 1]) + result
s -= 1
e -= 1
elif (dp[s - 1][e] > dp[s][e - 1]) :
result = str(b[e - 1]) + result
e -= 1
else :
result = str(a[s - 1]) + result
s -= 1
# Collect remaining character of first string
while (s > 0) :
result = str(a[s - 1]) + result
s -= 1
# Collect remaining character of second string
while (e > 0) :
result = str(b[e - 1]) + result
e -= 1
# Display calculated result
print(" Length : ", min)
print(" Result : ", result)
def main() :
task = Supersequence()
# Test A
# String a : abc
# String b : fab
# [fabc] Supersequence
# Result = 4
task.findSCS("abc", "fab")
# Test B
# String a : project
# String b : objects
# [probjects]
# Result : 9
task.findSCS("project", "objects")
# Test C
# String a : match
# String b : attack
# [mattachk,matatchk,mattackh] etc
# Result : 8 (length of Supersequence)
task.findSCS("match", "attack")
# Test D
# String a : abc
# String b : abc
# [abc] etc
# Result : 3
task.findSCS("abc", "abc")
if __name__ == "__main__": main()
Output
Given string a : abc
Given string b : fab
Length : 4
Result : fabc
Given string a : project
Given string b : objects
Length : 9
Result : probjects
Given string a : match
Given string b : attack
Length : 8
Result : mattackh
Given string a : abc
Given string b : abc
Length : 3
Result : abc
# Ruby program for
# Printing 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 findSCS(a, b)
n = a.length
m = b.length
result = ""
# 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")
min = dp[n][m]
s = n
e = m
while (s > 0 && e > 0)
if (a[s - 1] == b[e - 1])
# When both string character at position are same from end
result = a[s - 1].to_s + result
s -= 1
e -= 1
elsif (dp[s - 1][e] > dp[s][e - 1])
result = b[e - 1].to_s + result
e -= 1
else
result = a[s - 1].to_s + result
s -= 1
end
end
# Collect remaining character of first string
while (s > 0)
result = a[s - 1].to_s + result
s -= 1
end
# Collect remaining character of second string
while (e > 0)
result = b[e - 1].to_s + result
e -= 1
end
# Display calculated result
print(" Length : ", min, "\n")
print(" Result : ", result, "\n")
end
end
def main()
task = Supersequence.new()
# Test A
# String a : abc
# String b : fab
# [fabc] Supersequence
# Result = 4
task.findSCS("abc", "fab")
# Test B
# String a : project
# String b : objects
# [probjects]
# Result : 9
task.findSCS("project", "objects")
# Test C
# String a : match
# String b : attack
# [mattachk,matatchk,mattackh] etc
# Result : 8 (length of Supersequence)
task.findSCS("match", "attack")
# Test D
# String a : abc
# String b : abc
# [abc] etc
# Result : 3
task.findSCS("abc", "abc")
end
main()
Output
Given string a : abc
Given string b : fab
Length : 4
Result : fabc
Given string a : project
Given string b : objects
Length : 9
Result : probjects
Given string a : match
Given string b : attack
Length : 8
Result : mattackh
Given string a : abc
Given string b : abc
Length : 3
Result : abc
import scala.collection.mutable._;
/*
Scala program for
Printing 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 findSCS(a: String, b: String): Unit = {
var n: Int = a.length();
var m: Int = b.length();
var result: String = "";
// 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);
var min: Int = dp(n)(m);
var s: Int = n;
var e: Int = m;
while (s > 0 && e > 0)
{
if (a.charAt(s - 1) == b.charAt(e - 1))
{
// When both string character at position are same from end
result = a.charAt(s - 1).toString() + result;
s -= 1;
e -= 1;
}
else if (dp(s - 1)(e) > dp(s)(e - 1))
{
result = b.charAt(e - 1).toString() + result;
e -= 1;
}
else
{
result = a.charAt(s - 1).toString() + result;
s -= 1;
}
}
// Collect remaining character of first string
while (s > 0)
{
result = a.charAt(s - 1).toString() + result;
s -= 1;
}
// Collect remaining character of second string
while (e > 0)
{
result = b.charAt(e - 1).toString() + result;
e -= 1;
}
// Display calculated result
println(" Length : " + min);
println(" Result : " + result);
}
}
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.findSCS("abc", "fab");
// Test B
// String a : project
// String b : objects
// [probjects]
// Result : 9
task.findSCS("project", "objects");
// Test C
// String a : match
// String b : attack
// [mattachk,matatchk,mattackh] etc
// Result : 8 (length of Supersequence)
task.findSCS("match", "attack");
// Test D
// String a : abc
// String b : abc
// [abc] etc
// Result : 3
task.findSCS("abc", "abc");
}
}
Output
Given string a : abc
Given string b : fab
Length : 4
Result : fabc
Given string a : project
Given string b : objects
Length : 9
Result : probjects
Given string a : match
Given string b : attack
Length : 8
Result : mattackh
Given string a : abc
Given string b : abc
Length : 3
Result : abc
import Foundation;
/*
Swift 4 program for
Printing 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 findSCS(_ a1: String, _ b1: String)
{
let a = Array(a1);
let b = Array(b1);
let n: Int = a.count;
let m: Int = b.count;
var result: String = "";
// 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);
let min: Int = dp[n][m];
var s: Int = n;
var e: Int = m;
while (s > 0 && e > 0)
{
if (a[s - 1] == b[e - 1])
{
// When both string character at position are same from end
result = String(a[s - 1]) + result;
s -= 1;
e -= 1;
}
else if (dp[s - 1][e] > dp[s][e - 1])
{
result = String(b[e - 1]) + result;
e -= 1;
}
else
{
result = String(a[s - 1]) + result;
s -= 1;
}
}
// Collect remaining character of first string
while (s > 0)
{
result = String(a[s - 1]) + result;
s -= 1;
}
// Collect remaining character of second string
while (e > 0)
{
result = String(b[e - 1]) + result;
e -= 1;
}
// Display calculated result
print(" Length : ", min);
print(" Result : ", result);
}
}
func main()
{
let task: Supersequence = Supersequence();
// Test A
// String a : abc
// String b : fab
// [fabc] Supersequence
// Result = 4
task.findSCS("abc", "fab");
// Test B
// String a : project
// String b : objects
// [probjects]
// Result : 9
task.findSCS("project", "objects");
// Test C
// String a : match
// String b : attack
// [mattachk,matatchk,mattackh] etc
// Result : 8 (length of Supersequence)
task.findSCS("match", "attack");
// Test D
// String a : abc
// String b : abc
// [abc] etc
// Result : 3
task.findSCS("abc", "abc");
}
main();
Output
Given string a : abc
Given string b : fab
Length : 4
Result : fabc
Given string a : project
Given string b : objects
Length : 9
Result : probjects
Given string a : match
Given string b : attack
Length : 8
Result : mattackh
Given string a : abc
Given string b : abc
Length : 3
Result : abc
/*
Kotlin program for
Printing 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 findSCS(a: String, b: String): Unit
{
val n: Int = a.length;
val m: Int = b.length;
var result: String = "";
// Auxiliary space
var 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);
val min: Int = dp[n][m];
var s: Int = n;
var e: Int = m;
while (s > 0 && e > 0)
{
if (a.get(s - 1) == b.get(e - 1))
{
// When both string character at position are same from end
result = a.get(s - 1).toString() + result;
s -= 1;
e -= 1;
}
else if (dp[s - 1][e] > dp[s][e - 1])
{
result = b.get(e - 1).toString() + result;
e -= 1;
}
else
{
result = a.get(s - 1).toString() + result;
s -= 1;
}
}
// Collect remaining character of first string
while (s > 0)
{
result = a.get(s - 1).toString() + result;
s -= 1;
}
// Collect remaining character of second string
while (e > 0)
{
result = b.get(e - 1).toString() + result;
e -= 1;
}
// Display calculated result
println(" Length : " + min);
println(" Result : " + result);
}
}
fun main(args: Array < String > ): Unit
{
val task: Supersequence = Supersequence();
// Test A
// String a : abc
// String b : fab
// [fabc] Supersequence
// Result = 4
task.findSCS("abc", "fab");
// Test B
// String a : project
// String b : objects
// [probjects]
// Result : 9
task.findSCS("project", "objects");
// Test C
// String a : match
// String b : attack
// [mattachk,matatchk,mattackh] etc
// Result : 8 (length of Supersequence)
task.findSCS("match", "attack");
// Test D
// String a : abc
// String b : abc
// [abc] etc
// Result : 3
task.findSCS("abc", "abc");
}
Output
Given string a : abc
Given string b : fab
Length : 4
Result : fabc
Given string a : project
Given string b : objects
Length : 9
Result : probjects
Given string a : match
Given string b : attack
Length : 8
Result : mattackh
Given string a : abc
Given string b : abc
Length : 3
Result : abc
Time Complexity
The time complexity of the provided algorithm is O(n * m), where n and m are the lengths of the input strings
a
and b
. This is because the algorithm constructs a 2D dynamic programming table of size
(n+1) x (m+1) and fills it based on certain conditions. The space complexity is also O(n * m) due to the storage of
the dynamic programming table.
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