38 lines
1 KiB
Text
38 lines
1 KiB
Text
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
|