Longest common subsequence: Difference between revisions

Line 11:

=={{header|Ada}}==

Using recursion:

<lang ada>with Ada.Text_IO; use Ada.Text_IO;

with Ada.Text_IO; use Ada.Text_IO;

procedure Test_LCS is

Line 36:

Line 35:

begin

Put_Line (LCS ("thisisatest", "testing123testing"));

end Test_LCS;

end Test_LCS;</lang>

⚫

</lang>

Sample output:

<pre>

Line 43:

Line 41:

</pre>

Non-recursive solution:

<lang ada>with Ada.Text_IO; use Ada.Text_IO;

with Ada.Text_IO; use Ada.Text_IO;

procedure Test_LCS is

Line 88:

Line 85:

begin

Put_Line (LCS ("thisisatest", "testing123testing"));

end Test_LCS;

end Test_LCS;</lang>

⚫

</lang>

Sample output:

<pre>

Line 100:

Line 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>

<lang algol68>main:(

main:(

PROC lcs = (STRING a, b)STRING:

BEGIN

Line 115:

Line 110:

END # lcs #;

print((lcs ("thisisatest", "testing123testing"), new line))

⚫

)</lang>

)

⚫

</lang>

Output:

<pre>

Line 298:

Line 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

<pre>

⚫

longest xs ys = if length xs > length ys then xs else ys

lcs [] _ = []

Line 305:

Line 298:

lcs (x:xs) (y:ys)

| x == y = x : lcs xs ys

| otherwise = longest (lcs (x:xs) ys) (lcs xs (y:ys))

| otherwise = longest (lcs (x:xs) ys) (lcs xs (y:ys))</lang>

</pre>

Memoization (aka dynamic programming) of that uses ''zip'' to make both the index and the character available:

⚫

<lang haskell>import Data.Array

<pre>

⚫

import Data.Array

lcs xs ys = a!(0,0) where

Line 321:

Line 312:

f x y i j

| x == y = x : a!(i+1,j+1)

| otherwise = longest (a!(i,j+1)) (a!(i+1,j))

| otherwise = longest (a!(i,j+1)) (a!(i+1,j))</lang>

</pre>

Both solutions work of course not only with strings, but also with any other list. Example:

⚫

<lang haskell>*Main> lcs "thisisatest" "testing123testing"

<pre>

⚫

"tsitest"</lang>

⚫

*Main> lcs "thisisatest" "testing123testing"

"tsitest"

</pre>

=={{header|J}}==

lcs=: dyad define

<lang j>lcs=: dyad define

|.x{~ 0{"1 cullOne^:_ (\:~~ +/@|:) 4$.$. x =/ y

)

cullOne=: verb define

if. (#y) = First0=.0(= i. 1:) 1,*./|: 2 >/\ y

do. y else. y #~ 0 First0}(#y)#1 end.

⚫

)</lang>

)

=={{header|Java}}==

Line 391:

Line 379:

=={{header|Logo}}==

This implementation works on both words and lists.

<lang logo>to longest :s :t

to longest :s :t

output ifelse greater? count :s count :t [:s] [:t]

end

Line 400:

Line 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

end</lang>

</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:

Line 410:

lcs(`1234',`1224533324')

lcs(`thisisatest',`testing123testing')

lcs(`thisisatest',`testing123testing')</lang>

</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";

a = "thisisatest";

b = "testing123testing";

LongestCommonSequence[a, b]

LongestCommonSequence[a, b]</lang>

</lang>

gives:

<lang Mathematica>tsitest</lang>

Line 517:

Line 499:

return max(lcs(xstr, ys), lcs(xs, ystr), key=len)</lang>

Test it:

<lang python>if __name__=="__main__":

⚫

import doctest; doctest.testmod()</lang>

if __name__=="__main__":

⚫

import doctest; doctest.testmod()

</lang>

===Dynamic Programming===

Line 606:

Line 586:

===Recursion===

⚫

<lang slate>s1@(Sequence traits) longestCommonSubsequenceWith: s2@(Sequence traits)

⚫

s1@(Sequence traits) longestCommonSubsequenceWith: s2@(Sequence traits)

[

s1 isEmpty \/ s2 isEmpty ifTrue: [^ {}].

Line 616:

Line 595:

y: (s1 allButLast longestCommonSubsequenceWith: s2).

x length > y length ifTrue: [x] ifFalse: [y]]

].

].</lang>

</lang>

===Dynamic Programming===

⚫

<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:

Line 623:

index2: index2 - 1]]

] writingAs: s1) reverse

].

].</lang>

</lang>

=={{header|Tcl}}==