Longest common subsequence: Difference between revisions

'''<u>1234</u>'''

'''<u>12</u>'''245'''<u>3</u>'''332'''<u>4</u>'''

For a string example, consider the sequences "thisisatest" and "testing123testing". An LCS would be "tsitest":

'''<u>t</u>'''hi'''<u>si</u>'''sa'''<u>test</u>'''

 

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.

 

=={{header|Ada}}==

Using recursion:

 

procedure Test_LCS is

begin

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

<pre>

tsitest

</pre>

Non-recursive solution:

 

procedure Test_LCS is

begin

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

<pre>

tsitest

</pre>

=={{header|ALGOL 68}}==

{{trans|Ada}}

{{works with|ALGOL 68|Standard - no extensions to language used}}

{{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}}

PROC lcs = (STRING a, b)STRING:

BEGIN

END # lcs #;

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

<pre>

tsitest

</pre>

=={{header|AutoHotkey}}==

ahk forum: [http://www.autohotkey.com/forum/viewtopic.php?t=44657&start=135 discussion]

Loop % StrLen(a)+2 { ; Initialize

i := A_Index-1

}

Return t

 

=={{header|BASIC}}==

{{works with|QuickBasic|4.5}}

{{trans|Java}}

IF LEN(a$) = 0 OR LEN(b$) = 0 THEN

lcs$ = ""

END IF

END IF

 

=={{header|D}}==

 

}

 

 

}

 

 

=={{header|Fortran}}==

Using the <tt>iso_varying_string</tt> module which can be found [http://www.fortran.com/iso_varying_string.f95 here] (or equivalent module conforming to the ISO/IEC 1539-2:2000 API or to a subset according to the need of this code: <code>char</code>, <code>len</code>, <code>//</code>, <code>extract</code>, <code>==</code>, <code>=</code>)

 

use iso_varying_string

implicit none

end function lcs

 

 

=={{header|Haskell}}==

 

 

 

lcs [] _ = []

lcs (x:xs) (y:ys)

| x == y = x : lcs xs ys

 

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

 

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

f x y i j

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

 

=={{header|J}}==

 

=={{header|Java}}==

===Recursion===

This is not a particularly fast algorithm, but it gets the job done eventually. The speed is a result of many recursive function calls.

int aLen = a.length();

int bLen = b.length();

return (x.length() > y.length()) ? x : y;

}

 

===Dynamic Programming===

int[][] lengths = new int[a.length()+1][b.length()+1];

 

 

return sb.reverse().toString();

 

=={{header|Logo}}==

This implementation works on both words and lists.

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

end

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

 

A built-in function can do this for us:

b = "testing123testing";

gives:

Note that Mathematica also has a built-in function called LongestCommonSubsequence[a,b]:

 

''finds the longest sequence of contiguous or disjoint elements common to the strings or lists a and b.''

 

 

 

=={{header|OCaml}}==

===Recursion===

from Haskell

 

let rec lcs a b = match a, b with

x :: lcs xs ys

else

 

===Dynamic programming===

let xs = Array.of_list xs'

and ys = Array.of_list ys' in

done

done;

 

Because both solutions only work with lists, here are some functions to convert to and from strings:

let result = ref [] in

String.iter (fun x -> result := x :: !result)

let result = String.create (List.length lst) in

ignore (List.fold_left (fun i x -> result.[i] <- x; i+1) 0 lst);

 

Both solutions work. Example:

- : string = "tsitest"

</pre>

 

=={{header|Python}}==

===Recursion===

This solution is similar to the Haskell one. It is slow.

"""

>>> lcs('thisisatest', 'testing123testing')

x, xs, y, ys = xstr[0], xstr[1:], ystr[0], ystr[1:]

if x == y:

else:

Test it:

 

===Dynamic Programming===

for i, x in enumerate(a):

for j, y in enumerate(b):

lengths[i+1][j+1] = lengths[i][j] + 1

else:

 

===Recursion===

This solution is similar to the Haskell one. It is slow.

{{works with|Ruby|1.9}}

irb(main):001:0> lcs('thisisatest', 'testing123testing')

=> "tsitest"

=end

def lcs(xstr, ystr)

else

 

{{trans|Java}}

}

}

x -= 1

y -= 1

x -= 1

y -= 1

 

=={{header|Tcl}}==

===Recursive===

if {$a eq "" || $b eq ""} {return ""}

set a_ [string range $a 1 end]

return [expr {[string length $x] > [string length $y] ? $x :$y}]

}

===Dynamic===

{{works with|Tcl|8.5}}

namespace import ::tcl::mathop::+

namespace import ::tcl::mathop::-

set x $la

set y $lb

if {[lindex $lengths $x $y] == [lindex $lengths [- $x 1] $y]} {

incr x -1

}

return [string reverse $result]

===Performance Comparison===

637.5 microseconds per iteration

% time {r_lcs thisisatest testing123testing} 10