Question

A string x is called a supersequence of a string v if v is a subsequence of x. For example, ABLUE is a supersequence for BLUE and ABLE. Given strings v and w, devise an algorithm to find the shortest supersequence for both v and w.

Answer 1

The algorithm is given as:

ALGORITHM

Let U[0..m - 1] and V[0..n - 1] be two strings and m and n the length of U and V, respectively.

function ShortestCommonSupersequence(U, V, m, n) {

if (m == 0) return n

if (n == 0) return m

// If last characters are same, then add 1 to result and recur for U[]

if (U[m - 1] == V[n - 1])

return 1 + ShortestCommonSupersequence(U, V, m - 1, n - 1)

// Else find shortest of following two

// a) Remove last character from U and recur

// b) Remove last character from V and recur

else return 1 + min( ShortestCommonSupersequence(U, V, m - 1, n), ShortestCommonSupersequence(U, V, m, n - 1) );

}