The   shortest common supersequence   is a problem closely related to the   longest common subsequence,   which you can use as an external function for this task.



Task

Given two strings 



u


{\displaystyle u}

 and 



v


{\displaystyle v}

, find the shortest possible sequence 



s


{\displaystyle s}

, which is the shortest common super-sequence of 



u


{\displaystyle u}

 and 



v


{\displaystyle v}

 where both 



u


{\displaystyle u}

 and 



v


{\displaystyle v}

 are a subsequence of 



s


{\displaystyle s}

. Defined as such, 



s


{\displaystyle s}

 is not necessarily unique.

Demonstrate this by printing 



s


{\displaystyle s}

 where 



u
=


{\displaystyle u=}

“abcbdab” and 



v
=


{\displaystyle v=}

“bdcaba”.



Also see

 Wikipedia: shortest common supersequence 


with javascript_semantics
function longest_common_subsequence(sequence a, b)
    sequence res = ""
    if length(a) and length(b) then
        if a[$]=b[$] then
            res = longest_common_subsequence(a[1..-2],b[1..-2])&a[$]
        else
            sequence l = longest_common_subsequence(a,b[1..-2]),
                     r = longest_common_subsequence(a[1..-2],b)
            res = iff(length(l)>length(r)?l:r)
        end if
    end if
    return res
end function
 
function shortest_common_supersequence(string a, b)
    string lcs = longest_common_subsequence(a, b),
           scs = ""
    -- Consume lcs
    while length(lcs) do
        integer c = lcs[1]
        if a[1]==c and b[1]==c then
            -- Part of the lcs, so consume from all strings
            scs &= c
            lcs = lcs[2..$]
            a = a[2..$]
            b = b[2..$]
        elsif a[1]==c then
            scs &= b[1]
            b = b[2..$]
        else
            scs &= a[1]
            a = a[2..$]
        end if
    end while
    -- append remaining characters
    return scs & a & b
end function
 
?shortest_common_supersequence("abcbdab", "bdcaba")
?shortest_common_supersequence("WEASELS", "WARDANCE")
