user
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 {\displaystyle u}}
 and 

v
{\displaystyle {\displaystyle v}}
, find the shortest possible sequence 

s
{\displaystyle {\displaystyle s}}
, which is the shortest common super-sequence of 

u
{\displaystyle {\displaystyle u}}
 and 

v
{\displaystyle {\displaystyle v}}
 where both 

u
{\displaystyle {\displaystyle u}}
 and 

v
{\displaystyle {\displaystyle v}}
 are a subsequence of 

s
{\displaystyle {\displaystyle s}}
. Defined as such, 

s
{\displaystyle {\displaystyle s}}
 is not necessarily unique.

Demonstrate this by printing 

s
{\displaystyle {\displaystyle s}}
 where 

u
=
{\displaystyle {\displaystyle u=}}
“abcbdab” and 

v
=
{\displaystyle {\displaystyle v=}}
“bdcaba”.

Also see

* Wikipedia: shortest common supersequence
assistant
(formerly Perl 6)

Using 'lcs' routine from Longest common subsequence task

```
sub lcs(Str $xstr, Str $ystr) { # longest common subsequence
    return "" unless $xstr && $ystr;
    my ($x, $xs, $y, $ys) = $xstr.substr(0, 1), $xstr.substr(1), $ystr.substr(0, 1), $ystr.substr(1);
    return $x eq $y
        ?? $x ~ lcs($xs, $ys)
        !! max(:by{ $^a.chars }, lcs($xstr, $ys), lcs($xs, $ystr) );
}

sub scs ($u, $v) { # shortest common supersequence
    my @lcs = (lcs $u, $v).comb;
    my $pat = '(.*)' ~ join('(.*)',@lcs) ~ '(.*)';
    my $regex = "rx/$pat/".EVAL;
    my @u = ($u ~~ $regex).list;
    my @v = ($v ~~ $regex).list;
    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;

```

Output:

```
Strings: abcbdab bdcaba
Longest common subsequence:   bcba
Shortest common supersquence: abdcabdab
```