/*
Longest common subsequence in Picat.
From http://rosettacode.org/wiki/Longest_common_subsequence
"""
The longest common subsequence (or LCS) of groups A and B is the
longest group of elements from A and B that are common between the
two groups and in the same order in each group. For example, the
sequences "1234" and "1224533324" have an LCS of "1234":
1234
1224533324
For a string example, consider the sequences "thisisatest" and
"testing123testing". An LCS would be "tsitest":
thisisatest
testing123testing
In this puzzle, your code only needs to deal with strings. Write a
function which returns an LCS of two strings (case-sensitive).
You don't need to show multiple LCS's.
"""
Model created by Hakan Kjellerstrand, hakank@gmail.com
See also my Picat page: http://www.hakank.org/picat/
*/
main => go.
go =>
println("lcs():"),
time(println(lcs("thisisatest","testing123testing"))),
time(println(lcs("XMJYAUZ", "MZJAWXU"))),
time(println(lcs("1234", "1224533324"))),
println("lcs2():"),
time(println(lcs2("thisisatest","testing123testing"))),
time(println(lcs2("XMJYAUZ", "MZJAWXU"))),
time(println(lcs2("1234", "1224533324"))),
println("lcs3():"),
time(println(lcs3("thisisatest","testing123testing"))),
time(println(lcs3("XMJYAUZ", "MZJAWXU"))),
time(println(lcs3("1234", "1224533324"))),
println("lcs4():"),
time(println(lcs4("thisisatest","testing123testing"))),
time(println(lcs4("XMJYAUZ", "MZJAWXU"))),
time(println(lcs4("1234", "1224533324"))),
nl.
lcs(X,Y) = V =>
[C, _Len] = lcs_length(X,Y),
V = backTrace(C,X,Y,X.length+1,Y.length+1).
% From
% http:%en.wikipedia.org/wiki/Longest_common_subsequence
% with added trickery for a 1-based language.
%
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]].
% table
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.
% From the ADA solution
% Using table speed it up considerably.
table
lcs2(A,B) = V =>
ALen = A.length,
BLen = B.length,
A1 = [A[I] : I in 1..ALen-1],
B1 = [B[I] : I in 1..BLen-1],
if A == ""; B == "" then
V := ""
elseif A[ALen] == B[BLen] then
V := lcs2(A1, B1) ++ [A[ALen]]
else
X = lcs2(A, B1),
Y = lcs2(A1, B),
if X.length > Y.length then
V := X
else
V := Y
end
end.
%
% Inspired by the SETL version
% http:%rosettacode.org/wiki/Longest_common_subsequence#SETL
%
longest(A, B) = V =>
V := cond(A.length > B.length, A, B).
% without table lcs3/2 is faster than lcs2/2 without table,
% but slower than lcs/2.
table
lcs3(A, B) = V =>
if A == ""; B == "" then
V := ""
elseif A[1] == B[1] then
V := [A[1]] ++ lcs3(butfirst(A), butfirst(B))
else
V := longest(lcs3(butfirst(A), B), lcs3(A, butfirst(B)))
end.
% but first
butfirst(A) = [A[I] : I in 2..A.length].
% Rule based version of lcs3/2 (as a proof-of-concept).
% Note: using table don't work for some reason
% (and is therefore slower than lcs3/2)
table
lcs4(A, B) = "", (A == ""; B == "") => true.
lcs4(A, B) = [A[1]] ++ lcs4(butfirst(A), butfirst(B)), A[1] == B[1] => true.
lcs4(A, B) = longest(lcs4(butfirst(A), B), lcs4(A, butfirst(B))) => true.