Shortest common supersequence

Uses the lcs function defined here.

func scs(u, v) {
    var ls = lcs(u, v).chars
    var pat = Regex('(.*)'+ls.join('(.*)')+'(.*)')
    u.scan!(pat)
    v.scan!(pat)
    var ss = (u.shift + v.shift)
    ls.each { |c| ss += (c + u.shift + v.shift) }
    return ss
}
 
say scs("abcbdab", "bdcaba")

Output:

abdcabdab

Last updated