(phixonline)-->
with javascript_semantics
function LCSLength(sequence X, sequence Y)
sequence C = repeat(repeat(0,length(Y)+1),length(X)+1)
for i=1 to length(X) do
for j=1 to length(Y) do
if X[i]=Y[j] then
C[i+1][j+1] := C[i][j]+1
else
C[i+1][j+1] := max(C[i+1][j], C[i][j+1])
end if
end for
end for
return C
end function
function backtrack(sequence C, sequence X, sequence Y, integer i, integer j)
if i=0 or j=0 then
return ""
elsif X[i]=Y[j] then
return backtrack(C, X, Y, i-1, j-1) & X[i]
else
if C[i+1][j]>C[i][j+1] then
return backtrack(C, X, Y, i, j-1)
else
return backtrack(C, X, Y, i-1, j)
end if
end if
end function
function lcs(sequence a, sequence b)
return backtrack(LCSLength(a,b),a,b,length(a),length(b))
end function
constant tests = {{"1234","1224533324"},
{"thisisatest","testing123testing"}}
for i=1 to length(tests) do
string {a,b} = tests[i]
?lcs(a,b)
end for