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 


sub lcs { # longest common subsequence
    my( $u, $v ) = @_;
    return '' unless length($u) and length($v);
    my $longest = '';
    for my $first ( 0..length($u)-1 ) {
        my $char = substr $u, $first, 1;
        my $i = index( $v, $char );
        next if -1==$i;
        my $next = $char;
        $next .= lcs( substr( $u, $first+1), substr( $v, $i+1 ) ) unless $i==length($v)-1;
        $longest = $next if length($next) > length($longest);
    }
    return $longest;
}
 
sub scs { # shortest common supersequence
    my( $u, $v ) = @_;
    my @lcs = split //, lcs $u, $v;
    my $pat = "(.*)".join("(.*)",@lcs)."(.*)"; 
    my @u = $u =~ /$pat/;
    my @v = $v =~ /$pat/;
    my $scs = shift(@u).shift(@v);
    $scs .= $_.shift(@u).shift(@v) for @lcs;
    return $scs;
}
 
my $u = "abcbdab";
my $v = "bdcaba";
printf "Strings %s %s\n", $u, $v;
printf "Longest common subsequence:   %s\n", lcs $u, $v;
printf "Shortest common supersquence: %s\n", scs $u, $v;
 