29 lines
673 B
Text
29 lines
673 B
Text
lcs_wiki(X,Y) = V =>
|
|
[C, _Len] = lcs_length(X,Y),
|
|
V = backTrace(C,X,Y,X.length+1,Y.length+1).
|
|
|
|
lcs_length(X, Y) = V=>
|
|
M = X.length,
|
|
N = Y.length,
|
|
C = [[0 : J in 1..N+1] : I in 1..N+1],
|
|
foreach(I in 2..M+1,J in 2..N+1)
|
|
if X[I-1] == Y[J-1] then
|
|
C[I,J] := C[I-1,J-1] + 1
|
|
else
|
|
C[I,J] := max([C[I,J-1], C[I-1,J]])
|
|
end
|
|
end,
|
|
V = [C, C[M+1,N+1]].
|
|
|
|
backTrace(C, X, Y, I, J) = V =>
|
|
if I == 1; J == 1 then
|
|
V = ""
|
|
elseif X[I-1] == Y[J-1] then
|
|
V = backTrace(C, X, Y, I-1, J-1) ++ [X[I-1]]
|
|
else
|
|
if C[I,J-1] > C[I-1,J] then
|
|
V = backTrace(C, X, Y, I, J-1)
|
|
else
|
|
V = backTrace(C, X, Y, I-1, J)
|
|
end
|
|
end.
|