Anonymous user
Longest common subsequence: Difference between revisions
m
Fixed lang tags.
m (→{{trans|Ruby}}) |
m (Fixed lang tags.) |
||
Line 11:
=={{header|Ada}}==
Using recursion:
<lang ada>with Ada.Text_IO; use Ada.Text_IO;
procedure Test_LCS is
Line 36 ⟶ 35:
begin
Put_Line (LCS ("thisisatest", "testing123testing"));
end Test_LCS;</lang>
</lang>▼
Sample output:
<pre>
Line 43 ⟶ 41:
</pre>
Non-recursive solution:
<lang ada>with Ada.Text_IO; use Ada.Text_IO;
procedure Test_LCS is
Line 88 ⟶ 85:
begin
Put_Line (LCS ("thisisatest", "testing123testing"));
end Test_LCS;</lang>
</lang>▼
Sample output:
<pre>
Line 100 ⟶ 96:
{{works with|ALGOL 68G|Any - tested with release mk15-0.8b.fc9.i386}}
{{works with|ELLA ALGOL 68|Any (with appropriate job cards) - tested with release 1.8.8d.fc9.i386}}
<lang algol68>main:(
PROC lcs = (STRING a, b)STRING:
BEGIN
Line 115 ⟶ 110:
END # lcs #;
print((lcs ("thisisatest", "testing123testing"), new line))
▲)</lang>
</lang>▼
Output:
<pre>
Line 298 ⟶ 292:
The [http://en.wikipedia.org/wiki/Longest_common_subsequence#Solution_for_two_sequences Wikipedia solution] translates directly into Haskell, with the only difference that equal characters are added in front:
<lang haskell>longest xs ys = if length xs > length ys then xs else ys▼
▲longest xs ys = if length xs > length ys then xs else ys
lcs [] _ = []
Line 305 ⟶ 298:
lcs (x:xs) (y:ys)
| x == y = x : lcs xs ys
| otherwise = longest (lcs (x:xs) ys) (lcs xs (y:ys))</lang>
Memoization (aka dynamic programming) of that uses ''zip'' to make both the index and the character available:
<lang haskell>import Data.Array▼
▲import Data.Array
lcs xs ys = a!(0,0) where
Line 321 ⟶ 312:
f x y i j
| x == y = x : a!(i+1,j+1)
| otherwise = longest (a!(i,j+1)) (a!(i+1,j))</lang>
Both solutions work of course not only with strings, but also with any other list. Example:
<lang haskell>*Main> lcs "thisisatest" "testing123testing"▼
▲"tsitest"</lang>
▲*Main> lcs "thisisatest" "testing123testing"
=={{header|J}}==
▲)</lang>
=={{header|Java}}==
Line 391 ⟶ 379:
=={{header|Logo}}==
This implementation works on both words and lists.
<lang logo>to longest :s :t
output ifelse greater? count :s count :t [:s] [:t]
end
Line 400 ⟶ 387:
if equal? first :s first :t [output combine first :s lcs bf :s bf :t]
output longest lcs :s bf :t lcs bf :s :t
end</lang>
=={{header|M4}}==
<lang M4>define(`set2d',`define(`$1[$2][$3]',`$4')')▼
▲define(`set2d',`define(`$1[$2][$3]',`$4')')
define(`get2d',`defn($1[$2][$3])')
define(`tryboth',
Line 425 ⟶ 410:
lcs(`1234',`1224533324')
lcs(`thisisatest',`testing123testing')</lang>
Note: the caching (set2d/get2d) obscures the code even more than usual, but is necessary in order to get the second test to run in a reasonable amount of time.
=={{header|Mathematica}}==
A built-in function can do this for us:
<lang Mathematica>a = "thisisatest";
b = "testing123testing";
LongestCommonSequence[a, b]</lang>
gives:
<lang Mathematica>tsitest</lang>
Line 517 ⟶ 499:
return max(lcs(xstr, ys), lcs(xs, ystr), key=len)</lang>
Test it:
<lang python>if __name__=="__main__":
import doctest; doctest.testmod()</lang>▼
▲ import doctest; doctest.testmod()
===Dynamic Programming===
Line 606 ⟶ 586:
===Recursion===
{{trans|Java}}
<lang slate>s1@(Sequence traits) longestCommonSubsequenceWith: s2@(Sequence traits)▼
▲s1@(Sequence traits) longestCommonSubsequenceWith: s2@(Sequence traits)
[
s1 isEmpty \/ s2 isEmpty ifTrue: [^ {}].
Line 616 ⟶ 595:
y: (s1 allButLast longestCommonSubsequenceWith: s2).
x length > y length ifTrue: [x] ifFalse: [y]]
].</lang>
===Dynamic Programming===
{{trans|Ruby}}
<lang slate>s1@(Sequence traits) longestCommonSubsequenceWith: s2@(Sequence traits)▼
▲s1@(Sequence traits) longestCommonSubsequenceWith: s2@(Sequence traits)
[| lengths |
lengths: (ArrayMD newWithDimensions: {s1 length `cache. s2 length `cache} defaultElement: 0).
Line 646 ⟶ 623:
index2: index2 - 1]]
] writingAs: s1) reverse
].</lang>
=={{header|Tcl}}==
| |||