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 


class Link{ var len,letter,next;
   fcn init(l=0,c="",lnk=Void){ len,letter,next=l,c,lnk; }
}
fcn scs(x,y,out){
   lx,ly:=x.len(),y.len();
   lnk:=(ly+1).pump(List,'wrap(_){ (lx+1).pump(List(),Link.create) });
 
   foreach i in (ly){ lnk[i][lx]=Link(ly-i, y[i]) }
   foreach j in (lx){ lnk[ly][j]=Link(lx-j, x[j]) }
 
   foreach i,j in ([ly-1..0,-1],[lx-1..0,-1]){
      lp:=lnk[i][j];
      if (y[i]==x[j]){
	 lp.next  =lnk[i+1][j+1];
	 lp.letter=x[j];
      }else if(lnk[i][j+1].len < lnk[i+1][j].len){
	 lp.next  =lnk[i][j+1];
	 lp.letter=x[j];
      }else{
	 lp.next  =lnk[i+1][j];
	 lp.letter=y[i];
      }
      lp.len=lp.next.len + 1;
   }
 
   lp:=lnk[0][0]; while(lp){ out.write(lp.letter); lp=lp.next; }
   out.close()
}