Skip to main content

Shortest Common Supersequence

In computer science, the Shortest Common Supersequence (SCS) problem is a classic algorithmic problem. Given two strings, the goal is to find the shortest possible string that contains both input strings as subsequences.

Problem Statement

For example, let's consider two strings: string a and string b. The SCS is defined as the shortest string s such that both a and b are subsequences of s. In other words, s contains all the characters of a and b, preserving their relative order, but it may also contain additional characters.

The goal is to find the length of the SCS, as well as the SCS itself. If multiple SCS strings exist, any one of them can be considered as the result.

Algorithm

The algorithm for finding the length of the SCS can be implemented using dynamic programming. Let's consider two strings, a of length n and b of length m. We create a 2D array, dp, of size (n+1) x (m+1), where dp[i][j] represents the length of the SCS for the prefixes of a and b up to index i and j, respectively.

The algorithm follows these steps:

  1. Initialize the array dp with appropriate values:
    • dp[0][j] is set to j because when the length of a is zero, the SCS is obtained by adding all characters of b.
    • dp[i][0] is set to i because when the length of b is zero, the SCS is obtained by adding all characters of a.
  2. Iterate through each character of a and b:
    • If the characters at position i-1 in a and j-1 in b are the same, set dp[i][j] to dp[i-1][j-1] + 1. This means that the current characters contribute one character to the SCS.
    • Otherwise, set dp[i][j] to the minimum of dp[i][j-1] and dp[i-1][j] plus one. This accounts for the case where either a or b contributes a character to the SCS.
  3. The final result is stored in dp[n][m], where n and m are the lengths of strings a and b, respectively.
Code solution 
/*
    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

Explanation

Let's analyze the code and understand how it solves the SCS problem. The code uses dynamic programming to build a table, dp, to store the lengths of SCS for different prefixes of strings a and b.

The algorithm initializes the table by setting the values of dp[0][j] and dp[i][0] to represent the length of the SCS when one of the strings is empty. Then, it iterates through the characters of a and b to fill in the rest of the table.

For each pair of characters at positions i-1 and j-1 in a and b, respectively, the algorithm checks if the characters are the same. If they are, it adds one to the length of the SCS for the prefixes a and b without considering these characters (dp[i-1][j-1] + 1).

If the characters are different, the algorithm considers two options: either include the character from a or include the character from b. It chooses the minimum length between these two options plus one (minValue(dp[i][j-1], dp[i-1][j]) + 1).

Finally, the result is stored in dp[n][m], which represents the length of the SCS for the entire strings a and b. The algorithm outputs the given strings and the calculated result.

Time Complexity

The time complexity of this algorithm is O(n * m), where n and m are the lengths of strings a and b, respectively. This is because the algorithm iterates through all possible pairs of characters in a and b to fill in the dp table. Each iteration takes constant time operations, resulting in a total time complexity proportional to the product of the string lengths.

The space complexity of the algorithm is also O(n * m) since it uses a 2D array, dp, of size (n+1) x (m+1) to store the lengths of SCS for different prefixes of a and b.

The Shortest Common Supersequence problem is a well-known algorithmic problem that aims to find the shortest string containing two input strings as subsequences. The provided Java code demonstrates an efficient solution using dynamic programming. By building a table and considering different cases, the algorithm calculates the length of the SCS and outputs the result.

Understanding and implementing algorithms like the Shortest Common Supersequence can enhance your problem-solving skills and help you tackle similar challenges in the future.

Last updated on by Kalkicode




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