Longest common subsequence: Difference between revisions

=={{header|Picat}}==

Two methods are shown:

* The method from the Wikipedia page: lcs_wiki/2

* A rule based version (inspired by the SETL solution): lcs_rule/2.

<lang Picat>go =>

Tests = [["thisisatest","testing123testing"],

["XMJYAUZ", "MZJAWXU"],

["1234", "1224533324"],

["beginning-middle-ending","beginning-diddle-dum-ending"]

],

Funs = [lcs_wiki,lcs_rule],

foreach(Fun in Funs)

println(fun=Fun),

foreach(Test in Tests)

printf("%w : %w\n", Test, apply(Fun,Test[1],Test[2]))

end,

nl

end,

nl.

%

% The Wikipedia algorithm

% (with some added trickery for a 1-based language.

%

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.

% Rule based version (inspired by the SETL version)

table

lcs_rule(A, B) = "", (A == ""; B == "") => true.

lcs_rule(A, B) = [A[1]] ++ lcs_rule(butfirst(A), butfirst(B)), A[1] == B[1] => true.

lcs_rule(A, B) = longest(lcs_rule(butfirst(A), B), lcs_rule(A, butfirst(B))) => true.

% Return the longest string of A and B

longest(A, B) = cond(A.length > B.length, A, B).

% butfirst (everything except first element)

butfirst(A) = [A[I] : I in 2..A.length].</lang>

Output:

<pre>fun = lcs_wiki

[thisisatest,testing123testing] : tsitest

[XMJYAUZ,MZJAWXU] : MJAU

[1234,1224533324] : 1234

[beginning-middle-ending,beginning-diddle-dum-ending] : beginning-iddle-ending

fun = lcs_rule

[thisisatest,testing123testing] : tsitest

[XMJYAUZ,MZJAWXU] : MJAU

[1234,1224533324] : 1234

[beginning-middle-ending,beginning-diddle-dum-ending] : beginning-iddle-ending</pre>