Longest common subsequence: Difference between revisions
→{{header|Picat}}: Split into subsections. Added {{out}}
(→{{header|Picat}}: Split into subsections. Added {{out}}) |
|||
Line 2,255:
=={{header|Picat}}==
<lang Picat>lcs_wiki(X,Y) = V => ▼
<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).
Line 2,309 ⟶ 2,285:
V = backTrace(C, X, Y, I-1, J)
end
end.</lang>
===Rule-based===
{{trans|SETL}}
<lang Picat>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.
Line 2,323 ⟶ 2,300:
butfirst(A) = [A[I] : I in 2..A.length].</lang>
===Test===
▲<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.</lang>
{{out}}
<pre>fun = lcs_wiki
[thisisatest,testing123testing] : tsitest
|