Longest common subsequence: Difference between revisions

{{task}}[[Category:Recursion]][[Category:Memoization]]

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

 

For more information on this problem please see [[wp:Longest_common_subsequence_problem|Wikipedia]].

 

=={{header|Ada}}==

Using recursion:

 

procedure Test_LCS is

begin

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

{{out}}

<pre>

</pre>

Non-recursive solution:

 

procedure Test_LCS is

begin

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

{{out}}

<pre>

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

{{out}}

<pre>

tsitest

</pre>

=={{header|APL}}==

{{works with|Dyalog APL}}

⎕IO←0

betterof←{⊃(</+/¨⍺ ⍵)⌽⍺ ⍵} ⍝ better of 2 selections

this ∇ 1↓[1]⍵ ⍝ keep looking

}sstt

 

=={{header|AutoHotkey}}==

{{trans|Java}} using dynamic programming<br>

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|BBC BASIC}}==

This makes heavy use of BBC BASIC's shortcut '''LEFT$(a$)''' and '''RIGHT$(a$)''' functions.

PRINT FNlcs("thisisatest", "testing123testing")

END

y$ = FNlcs(LEFT$(a$), b$)

IF LEN(y$) > LEN(x$) SWAP x$,y$

'''Output:'''

<pre>

tsitest

</pre>

 

=={{header|Bracmat}}==

= A a ta B b tb prefix

. !arg:(?prefix.@(?A:%?a ?ta).@(?B:%?b ?tb))

& :?lcs

& LCS$(.thisisatest.testing123testing)

{{out}}

<pre>max 7 lcs t s i t e s t</pre>

 

=={{header|C}}==

#include <stdlib.h>

 

return t;

}

Testing

char a[] = "thisisatest";

char b[] = "testing123testing";

printf("%.*s\n", t, s); // tsitest

return 0;

 

 

 

 

'''Hunt and Szymanski algorithm'''

#include <string>

#include <memory> // for shared_ptr<>

#include <iostream>

#include <deque>

#include <algorithm> // for lower_bound()

 

using namespace std;

class LCS {

protected:

class Pair {

public:

 

typedef deque<shared_ptr<Pair>> PAIRS;

typedef deque<uint32_t> INDEXES;

typedef deque<INDEXES*> MATCHES;

 

 

//

// such that the LCS of s1[0:index1] and s2[0:index2] has length index3 + 1

//

uint32_t index1 = 0;

 

 

 

 

}

}

 

index1++;

} // next index1

 

*pairs = Pair::Reverse(last);

}

 

return length;

}

 

//

//

// The lookup time can be assumed constant in the case of characters.

// time will be O(log(m+n)), at most.

//

const string& s1, const string& s2) {

uint32_t index = 0;

for (const auto& it : s2)

 

for (const auto& it : s1) {

}

}

 

bool right, const string& s1, const string& s2) {

string buffer;

 

public:

shared_ptr<Pair> pairs; // obtain the LCS as index pairs

return Select(pairs, length, false, s1, s2);

}

'''Example''':

 

 

=={{header|Clojure}}==

Based on algorithm from Wikipedia.

 

(def lcs

(memoize

(fn [[x & xs] [y & ys]]

(= x y) (cons x (lcs xs ys))

 

=={{header|CoffeeScript}}==

 

lcs = (s1, s2) ->

len1 = s1.length

s1 = "thisisatest"

s2 = "testing123testing"

 

=={{header|Common Lisp}}==

Here's a memoizing/dynamic-programming solution that uses an <var>n &times; m</var> array where <var>n</var> and <var>m</var> are the lengths of the input arrays. The first return value is a sequence (of the same type as array1) which is the longest common subsequence. The second return value is the length of the longest common subsequence.

(let* ((l1 (length array1))

(l2 (length array2))

b)))))))))

(destructuring-bind (seq len) (lcs 0 0)

 

For example,

 

 

produces the two values

 

 

===An alternative adopted from Clojure===

Here is another version with its own memoization macro:

 

(let ((hash-name (gensym)))

`(let ((,hash-name (make-hash-table :test 'equal)))

((equal (car xs) (car ys)) (cons (car xs) (lcs (cdr xs) (cdr ys))))

(t (longer (lcs (cdr xs) ys)

 

When we test it, we get:

 

 

 

=={{header|D}}==

 

===Recursive version===

 

T[] lcs(T)(in T[] a, in T[] b) pure nothrow @safe {

void main() {

lcs("thisisatest", "testing123testing").writeln;

{{out}}

<pre>tsitest</pre>

===Faster dynamic programming version===

The output is the same.

 

T[] lcs(T)(in T[] a, in T[] b) pure /*nothrow*/ {

void main() {

lcs("thisisatest", "testing123testing").writeln;

 

===Hirschberg algorithm version===

Adapted from Python code: http://wordaligned.org/articles/longest-common-subsequence

 

 

uint[] lensLCS(R)(R xs, R ys) pure nothrow @safe {

void main() {

lcsString("thisisatest", "testing123testing").writeln;

 

=={{header|Dart}}==

 

String lcsRecursion(String a, String b) {

print("lcsRecursion('x', 'x') = ${lcsRecursion('x', 'x')}");

}

{{out}}

<pre>lcsDynamic('1234', '1224533324') = 1234

lcsRecursion('', 'x') =

lcsRecursion('x', 'x') = x</pre>

 

=={{header|Egison}}==

 

(define $common-seqs

(lambda [$xs $ys]

 

(define $lcs (compose common-seqs rac))

'''Output:'''

> (lcs "thisisatest" "testing123testing"))

"tsitest"

 

=={{header|Elixir}}==

end

defp lcs_length([h|st]=s,[h|tt]=t,cache) do

{l,c} = lcs_length(st,tt,cache)

end

defp lcs_length([_sh|st]=s,[_th|tt]=t,cache) do

else

{l1,c1} = lcs_length(s,tt,cache)

{l2,c2} = lcs_length(st,t,c1)

end

end

def lcs(s,t) do

{_,c} = lcs_length(s,t,Map.new)

end

defp lcs([h|st],[h|tt],cache,acc), do: lcs(st,tt,cache,[h|acc])

defp lcs([_sh|st]=s,[_th|tt]=t,cache,acc) do

lcs(s,tt,cache,acc)

else

end

 

 

{{out}}

1234

</pre>

 

=={{header|Erlang}}==

This implementation also includes the ability to calculate the length of the longest common subsequence. In calculating that length, we generate a cache which can be traversed to generate the longest common subsequence.

module(lcs).

-compile(export_all).

lcs(ST,T,Cache,Acc)

end.

'''Output:'''

77> lcs:lcs("thisisatest","testing123testing").

"tsitest"

78> lcs:lcs("1234","1224533324").

"1234"

 

We can also use the process dictionary to memoize the recursive implementation:

 

lcs(Xs0, Ys0) ->

CacheKey = {lcs_cache, Xs0, Ys0},

Result

end.

 

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

===Recursion===

Brute force

aLen := len(a)

bLen := len(b)

}

return y

 

===Dynamic Programming===

arunes := []rune(a)

brunes := []rune(b)

}

return string(s)

 

=={{header|Groovy}}==

Recursive solution:

if (xstr == "" || ystr == "") {

return "";

 

println(lcs("1234", "1224533324"));

{{out}}

<pre>1234

The [[wp:Longest_common_subsequence#Solution_for_two_sequences|Wikipedia solution]] translates directly into Haskell, with the only difference that equal characters are added in front:

 

 

lcs [] _ = []

lcs (x:xs) (y:ys)

| x == y = x : lcs xs ys

 

A Memoized version of the naive algorithm.

 

 

lcs = memoize lcsm

maxl x y = if length x > length y then x else y

memoize = M.memo2 mString mString

 

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)

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

The dynamic programming version without using arrays:

 

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

f [a,b] [c,d]

| null a = longest b c: [b]

 

 

Simple and slow solution:

 

import Data.List

 

lcs xs ys = maximumBy (comparing length) $ intersect (subsequences xs) (subsequences ys)

 

{{out}}

<pre>"tsitest"</pre>

{{libheader|Icon Programming Library}} [http://www.cs.arizona.edu/icon/library/src/procs/strings.icn Uses deletec from strings]

 

LCSTEST("thisisatest","testing123testing")

LCSTEST("","x")

 

return if *(x := lcs(a,b[1:-1])) > *(y := lcs(a[1:-1],b)) then x else y # divide, discard, and keep longest

{{out}}

<pre>lcs( "thisisatest", "testing123testing" ) = "tsitest"

 

=={{header|J}}==

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

)

 

 

Here's [[Longest_common_subsequence/J|another approach]]:

 

common=: 2 2 <@mergeSq@,;.3^:_ [: (<@#&.> i.@$) =/

 

Example use (works with either definition of lcs):

 

 

'''Dynamic programming version'''

upd=:{:@[,~ ({.@[ ,&.> {:@])`({:@[ longest&.> {.@])@.(0 = #&>@{.@[)

'''Output:'''

1234

 

'thisisatest' lcs 'testing123testing'

 

'''Recursion'''

 

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

{{trans|Java}}

This is more or less a translation of the recursive Java version above.

var aSub = a.substr(0, a.length - 1);

var bSub = b.substr(0, b.length - 1);

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

}

 

ES6 recursive implementation

 

 

if (!xx.length || !yy.length) { return ''; }

 

 

===Dynamic Programming===

This version runs in O(mn) time and consumes O(mn) space.

Factoring out loop edge cases could get a small constant time improvement, and it's fairly trivial to edit the final loop to produce a full diff in addition to the lcs.

var s,i,j,m,n,

lcs=[],row=[],c=[],

}

return lcs.join('');

 

'''BUG note: In line 6, m and n are not yet initialized, and so x and y are never swapped.'''

 

The final loop can be modified to concatenate maximal common substrings rather than individual characters:

while(i>-1&&j>-1){

switch(c[i][j]){

}

}

 

===Greedy Algorithm===

This is an heuristic algorithm that won't always return the correct answer, but is significantly faster and less memory intensive than the dynamic programming version, in exchange for giving up the ability to re-use the table to find alternate solutions and greater complexity in generating diffs. Note that this implementation uses a binary buffer for additional efficiency gains, but it's simple to transform to use string or array concatenation;

var p1, i, idx,

symbols = {},

return pos;

}

 

 

=={{header|jq}}==

Naive recursive version:

if (xstr == "" or ystr == "") then ""

else

| if ($one|length) > ($two|length) then $one else $two end

end

 

Example:

# jq -n -f lcs-recursive.jq

"1234"

 

=={{header|Liberty BASIC}}==

'variation of BASIC example

w$="aebdef"

END IF

END FUNCTION

 

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

 

=={{header|Lua}}==

if #a == 0 or #b == 0 then

return ""

end

 

 

=={{header|M4}}==

define(`get2d',`defn($1[$2][$3])')

define(`tryboth',

lcs(`1234',`1224533324')

 

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|Maple}}==

> StringTools:-LongestCommonSubSequence( "thisisatest", "testing123testing" );

"tsitest"

 

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|Nim}}==

===Recursion===

{{trans|Python}}

if x == "" or y == "":

return ""

 

echo lcs("1234", "1224533324")

 

===Dynamic Programming===

{{trans|Python}}

for i in 0 .. a.len:

 

for i, x in a:

 

echo lcs("1234", "1224533324")

 

=={{header|OCaml}}==

===Recursion===

from Haskell

 

let rec lcs a b = match a, b with

x :: lcs xs ys

else

 

===Memoized recursion===

let lcs xs ys =

let cache = Hashtbl.create 16 in

result

in

 

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

 

Recursive solution:

fun {LCS Xs Ys}

case [Xs Ys]

end

in

 

=={{header|Pascal}}==

{{trans|Fortran}}

function lcs(a, b: string): string;

s2 := '1224533324';

writeln (lcs(s1, s2));

{{out}}

<pre>:> ./LongestCommonSequence

 

=={{header|Perl}}==

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

=={{header|PicoLisp}}==

(when A

(conc

(commonSequences

(chop "thisisatest")

{{out}}

<pre>-> ("t" "s" "i" "t" "e" "s" "t")</pre>

 

=={{header|Prolog}}==

===Recursive Version===

First version:

time(lcs("thisisatest", "testing123testing", Lcs)),

writef('%s',[Lcs]).

length(L1,Length1),

length(L2,Length2),

Second version, with memoization:

:- dynamic lcs_db/3.

 

length(L1,Length1),

length(L2,Length2),

{{out|Demonstrating}}

Example for "beginning-middle-ending" and "beginning-diddle-dum-ending" <BR>

First version :

% 10,875,184 inferences, 1.840 CPU in 1.996 seconds (92% CPU, 5910426 Lips)

Second version which is much faster :

% 2,376 inferences, 0.010 CPU in 0.003 seconds (300% CPU, 237600 Lips)

 

=={{header|PureBasic}}==

{{trans|Basic}}

Protected x$ , lcs$

If Len(a$) = 0 Or Len(b$) = 0

OpenConsole()

PrintN( lcs("thisisatest", "testing123testing"))

 

=={{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):

else:

lengths[i+1][j+1] = max(lengths[i+1][j], lengths[i][j+1])

 

=={{header|Racket}}==

(define (longest xs ys)

(if (> (length xs) (length ys))

(list->string (lcs/list (string->list sx) (string->list sy))))

 

{{out}}

<pre>"tsitest"></pre>

 

=={{header|REXX}}==

<pre>

</pre>

<pre>

</pre>

 

This solution is similar to the Haskell one. It is slow (The time complexity is exponential.)

{{works with|Ruby|1.9}}

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

=> "tsitest"

[lcs(xstr, ys), lcs(xs, ystr)].max_by {|x| x.size}

end

 

===Dynamic programming===

Walker class for the LCS matrix:

 

SELF, LEFT, UP, DIAG = [0,0], [0,-1], [-1,0], [-1,-1]

puts lcs('thisisatest', 'testing123testing')

puts lcs("rosettacode", "raisethysword")

 

{{out}}

 

=={{header|Run BASIC}}==

b$ = "cacbac"

print lcs$(a$,b$)

END IF

[ext]

 

else {

}

}

}

 

 

}

 

=={{header|Scheme}}==

Port from Clojure.

 

;; using srfi-69

(define (memoize proc)

'()))

'()))))

 

Testing:

 

(test-group

(lcs '(a b d e f g h i j)

'(A b c d e f F a g h j))))

 

=={{header|Seed7}}==

 

const func string: lcs (in string: a, in string: b) is func

writeln(lcs("thisisatest", "testing123testing"));

writeln(lcs("1234", "1224533324"));

 

Output:

tsitest

1234

</pre>

 

=={{header|SETL}}==

Recursive; Also works on tuples (vectors)

return if #a > #b then a else b end;

end .longest;

return lcs(a(2..), b) .longest lcs(a, b(2..));

end;

 

=={{header|Sidef}}==

 

 

 

if (x == y) {

x + lcs(xs, ys)

} else {

}

}

 

{{out}}

<pre>

===Recursion===

{{trans|Java}}

[

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

y: (s1 allButLast longestCommonSubsequenceWith: s2).

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

===Dynamic Programming===

{{trans|Ruby}}

[| lengths |

lengths: (ArrayMD newWithDimensions: {s1 length `cache. s2 length `cache} defaultElement: 0).

index2: index2 - 1]]

] writingAs: s1) reverse

=={{header|Swift}}==

===Recursion===

 

===Dynamic Programming===

lens[i + 1][j + 1] = lens[i][j] + 1

} else {

}

while x != 0 && y != 0 {

if lens[x][y] == lens[x - 1][y] {

} else if lens[x][y] == lens[x][y - 1] {

} else {

}

}

 

=={{header|Tcl}}==

===Recursive===

{{trans|Java}}

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

set a_ [string range $a 1 end]

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

}

===Dynamic===

{{trans|Java}}

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

 

=={{header|Ursala}}==

This uses the same recursive algorithm as in the Haskell example,

and works on lists of any type.

 

test program:

 

{{out}}

<pre>'tsitest'</pre>

 

=={{header|zkl}}==

This is quite vile in terms of [time] efficiency, another algorithm should be used for real work.

{{trans|D}}

if(not a or not b) return("");

if (a[0]==b[0]) return(a[0] + self.fcn(a[1,*],b[1,*]));

return(fcn(x,y){if(x.len()>y.len())x else y}(lcs(a,b[1,*]),lcs(a[1,*],b)))

The last line looks strange but it is just return(lambda longest(lcs.lcs))

{{out}}