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 


ClearAll[RosettaShortestCommonSuperSequence]
RosettaShortestCommonSuperSequence[aa_String, bb_String] := 
 Module[{lcs, scs, a = aa, b = bb},
  lcs = LongestCommonSubsequence[aa, bb];
  scs = "";
  While[StringLength[lcs] > 0,
   If[StringTake[a, 1] == StringTake[lcs, 1] \[And] StringTake[b, 1] == StringTake[lcs, 1],
    scs = StringJoin[scs, StringTake[lcs, 1]];
    lcs = StringDrop[lcs, 1];
    a = StringDrop[a, 1];
    b = StringDrop[b, 1];
    ,
    If[StringTake[a, 1] == StringTake[lcs, 1],
     scs = StringJoin[scs, StringTake[b, 1]];
     b = StringDrop[b, 1];
     ,
     scs = StringJoin[scs, StringTake[a, 1]];
     a = StringDrop[a, 1];
     ]
    ]
   ];
  StringJoin[scs, a, b]
  ]
RosettaShortestCommonSuperSequence["abcbdab", "bdcaba"]
RosettaShortestCommonSuperSequence["WEASELS", "WARDANCE"]