Shortest Common Supersequence

Let’s consider two substrings of length m and n, respectively. Now we can have two situations:-

Both the strings end with the same element:

So for finding their shortest common supersequence, what we have to do is we will shorten each string by removing the last element. Then we will find the shortest common supersequence of shortened lines, and then the removed element will be appended to the shortest common supersequence.

SCS(A[1…..m], B[1…...n]) = SCS(A[1….m-1], B[1...n-1]) + A[m]

Suppose two given strings are not ending at the same character:

In this situation the shortest common supersequence will be the shorter of the two sequences SCS(A[1...m-1], B[1..n]) + A[m] and SCS(A[1...m], B[1...n-1]) + B[n].

Algorithm:

Function shortestSupersequenceRec

Function arguments - string ‘A’, string ‘B’, integer ‘N’ representing the length of A’s prefix to be considered, integer ‘M’ representing the length of B’s prefix to be considered.
Returns - Shortest supersequence of A[1,2,...N] and B[1,2,...M].

• If n == 0
  • Return prefix of B of length m
• If m == 0
  • Return prefix of A of length n
• If a[n-1] == b[n-1]
  • Return shortestSupersequenceRec(a, b, n-1, m-1) + a[n-1]
• Declare and initialize string sa = shortestSupersequenceRec(a, b, n-1, m) + a[n-1]
• Declare and initialize string sb = shortestSupersequenceRec(a, b, n, m-1) + b[m-1]
• Return the shorter string out of sa and sb

Given Function

• Declare and initialize integers n = length of A and m = length of B
• Return shortestSupersequenceRec(a, b, n, m)

We are doing a lot of duplicate calls to the recursive function and calculating the same thing multiple times. We can eliminate this by using a table containing answers for all the previous calls to the function. We will return the value saved in the lookup table if we have already solved it for a particular prefix pair. Implementation details are as per the following algorithm.

Algorithm:

Function shortestSupersequenceRec

Function arguments - string ‘A’, string ‘B’, integer ‘N’ representing the length of A’s prefix to be considered, integer ‘M’ representing the length of B’s prefix to be considered.
Returns - Length of the shortest supersequence of A[1,2,...N] and B[1,2,...M].

• If n == 0
  • Return m
• If m == 0
  • Return n
• If table[n][m] is not equal to infinity
  • Return table[n][m]
• If a[n-1] == b[n-1]
  • Set table[n][m] = shortestSupersequenceRec(a, b, n-1, m-1) + 1
  • Return table[n][m]
• Set table[n][m] = 1 + min(shortestSupersequenceRec(a, b, n-1, m), shortestSupersequenceRec(a, b, n, m-1))
• Return table[n][m]

Function backtrack

Function arguments - 2D lookup table, string ‘A’, string ‘B’

Returns - Shortest supersequence by backtracking lookup table.

• Declare and initialize string ans to be empty
• Declare and initialize integers n = length of A and m = length of B
• While n > 0 AND m > 0
  • If a[n-1] == b[m-1]
    • Append a[n-1] to string ans
    • Decrement n and m
  • Else if table[n-1][m] < table[n][m-1]
    • Append a[n-1] to string ans
    • Decrement n
  • Else
    • Append b[m-1] to string ans
    • Decrement m
• While n > 0
  • Append a[n-1] to string ans
  • Decrement n
• While m > 0
  • Append b[m-1] to string ans
  • Decrement m
• Reverse ans
• Return ans

Given Function

• Declare and initialize integer n = length of A and m = length of B
• Declare 2D lookup table of size n+1 * m+1 initialized to infinity.
• shortestSuperSequence(a, b, table, n, m)
• Return backtrack(dp, a, b)

We are doing a lot of duplicate calls to the recursive function and calculating the same thing multiple times. We can eliminate this by using an iterative Dynamic Programming approach.

We will iterate on all the prefixes of strings in increasing order of their lengths and store the minimum length of supersequence for each of the prefix values, which will be used to calculate the minimum length for coins for bigger subarrays. After we fill the DP table, we backtrack our decisions by traversing in DP from (n,m) to (0,0) and retrieving the actual shortest supersequence. We will be retrieving supersequence in reverse order. We need to reverse it before returning. Implementation details are as per the following algorithm.

Algorithm:

Function backtrack

Function arguments - 2D DP table, string ‘A’, string ‘B’

Returns - Shortest supersequence by backtracking DP table.

• Declare and initialize string ans to be empty
• Declare and initialize integers n = length of A and m = length of B
• While n > 0 AND m > 0
  • If a[n-1] == b[m-1]
    • Append a[n-1] to string ans
    • Decrement n and m
  • Else if dp[n-1][m] < dp[n][m-1]
    • Append a[n-1] to string ans
    • Decrement n
  • Else
    • Append b[m-1] to string ans
    • Decrement m
• While n > 0
  • Append a[n-1] to string ans
  • Decrement n
• While m > 0
  • Append b[m-1] to string ans
  • Decrement m
• Reverse ans
• Return ans

Given Function

• Declare and initialize integer n = length of A and m = length of B
• Declare 2D DP table of size n+1 * m+1
• Iterate over i from 0 to n
  • Set dp[i][0] = i
• Iterate over i from 0 to m
  • Set dp[0][i] = i
• Iterate over i from 1 to n
  • Iterate over j from 1 to m
    • If a[i-1] == b[j-1]
      • Set dp[i][j] = dp[i-1][j-1] + 1
    • Else
      • Set dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + 1
• Return backtrack(dp, a, b)