Printing Shortest Common Supersequence

Here given code implementation process.

/*
    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

« Previous Next »

Dynamic Programming

Word Break Problem

Find the length of longest arithmetic progression

Rod Cutting Problem

Min cost path in matrix

Levenshtein edit distance

Binomial coefficient using dynamic programming

Longest Bitonic Subsequence

Count the number of longest increasing subsequence

Count the minimum number of elements required to given sum

Coin change problem using dynamic programming

Equal subset sum partition

Calculating edit distance using dynamic programming

0-1 knapsack problem using dynamic programming

Program for minimum number of jumps to reach the end

Subset sum problem using dynamic programming

Longest common substring using dynamic programming

Newman-conway sequence program

Print Longest common subsequence

Longest common subsequence of three sequences

Longest palindromic substring using dynamic programming

Palindrome partition using dynamic programming

Maximum sum of pairs with specific difference using dynamic programming

Possible decodings of given digits using dynamic programming

Find maximum possible stolen value from houses

Find maximum sum bitonic sub sequence using dynamic programming

Maximum sum bitonic subarray using dynamic programming

Tiling problem using dynamic programming

Count prime numbers between two numbers

Golomb sequence using dynamic programming

Maximum sum increasing subsequence using dynamic programming

Distinct subsequences using dynamic programming

Count number of palindromic path in a matrix

Largest submatrix with zero sum using dynamic programming

Climbing stairs using dynamic programming

Find prime numbers between two numbers

Shortest uncommon subsequence using dynamic programming

Bell Triangle

Bernoulli's triangle

Prime factorization using dynamic programming

Shortest Common Supersequence

Maximum path sum in a triangle

Printing Shortest Common Supersequence

Friends Pairing Problem

Matrix chain multiplication using dynamic programming

Count subarrays with equal number of 1’s and 0’s

Count strictly decreasing subarrays

Frequency of maximum occurring subsequence in given string

Find the frequency of subsequence in given string

Count strictly increasing subarrays by using dynamic programming

Stern's Diatomic Series

Length of longest increasing subsequence

Find circular longest increasing subsequence

Efficiently find length of longest Increasing Subsequence

Longest palindromic subsequence using dynamic programming

Count subarrays with same even and odd elements

Maximum product cutting using dynamic programming

Gold Mine Problem

Printing brackets in matrix chain multiplication

Count all distinct combinations of sum x using n natural number

Print Ugly Numbers

Fibonacci series

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.

New Comment

Name