Question

Given two strings X and Y of length n and m respectively, design a dynamic
programming based algorithm to finnd a super-string Z of minimum length such that both
X and Y are subsequence of Z. Note that characters in X and Y do not need to appear
consecutively in Z as long as they appear in the same order in Z as in X or Y . Design an other
algorithm for solving the same problem but with three input strings, W;X; Y , i.e., finding the
minimum length super-string for three strings. Can your algorithm be extended to k input
strings? If so, what would be the running time and space complexities of your algorithm.

Answer 1

At first we will try to get a solution for 2 strings, we will create a function that will return string which is shortest common supersequence of input strings.

the following code is in python.

def shortestSuperSeq(x, y) :
    m = len(x)
    n = len(y)

    # dp[i][j] contains length of shortest

    dp = [[0 for i in range(n + 1)] for j in range(m + 1)]

    # Initialising 1st row and 1st column
    for i in range(m + 1):
        dp[0][i] = i
    for i in range(n + 1):
        dp[i][0] = i
    # filling the table same as LCS program
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if x[i - 1] == y[j - 1]:
                dp[i][j] = 1 + dp[i - 1][j - 1]
            else :
                dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1])

    # Extracting superSeq

    # dp[m][n] stores the length of the
    # shortest supersequence of X and Y
    index = dp[m][n]

    # string to store the shortest supersequence using backtracking
    string = ""

    # Start from the bottom right corner and one by one pushing characters in output string,
    i = m
    j = n
    while i > 0 and j > 0:

        # If current character in X and Y are same, then current character is part of shortest superseq
        if x[i - 1] == y[j - 1]:
            # add current character in result
            string += x[i - 1]
            # reducing values of i, j and index
            i -= 1
            j -= 1
            index -= 1

        # If current character in X and Y are different
        elif dp[i - 1][j] > dp[i][j - 1]:

            # add current character of Y in result
            string += y[j - 1]

            # reduce values of j and index
            j -= 1
            index -= 1
        else :

            # add current character of X in result
            string += x[i - 1]

            # reduce values of i and index
            i -= 1
            index -= 1
    # If X reaches its end, put remaining characters
    # of Y in the result string
    while j > 0:
        string += y[j - 1]
        j -= 1
        index -= 1

    # If Y reaches its end, put remaining characters
    # of X in the result string
    while i > 0 :
        string += x[i - 1]
        i -= 1
        index -= 1

    string = list(string)
    # reverse the string and return it
    string.reverse()
    return ''.join(string)

Now if you want to generalise this for 3 or K number of strings. say S1, S2, S3 be input strings

Then at first call function shortestSpuerSeq for the first two strings S1 and S2, store the result in a variable say ans1

after that call the function for S1 and S3, store the result in a vriable say ans2.

Finally call the function for ans1 and ans2. that will be required ans.

In similar fashion generliase it for K number of strings keep removing common subsequnces taking 1 string as base.

Assuming k to be 4 and say input strings be s1, s2, s3, s4.

then fun(s1, s2)--> ans12

fun(s1, s3) --> ans13

fun(s1, s4) --> ans14

now

fun(ans12, ans13) --> f_ans1

fun(ans12, ans14) --> f_ans2

finally.

fun(f_ans1, f_ans2) --> this will finally return the required ans

Time complexity for k strings will be O( k² * n²) where k is number of strings and n is length of string.

And space complexity will be O(n²)