28 lines
728 B
Text
28 lines
728 B
Text
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()
|
|
}
|