Longest common subsequence: Difference between revisions

'''Introduction'''

 

 

The [http://en.wikipedia.org/wiki/Longest_common_subsequence_problem '''Longest Common Subsequence'''] ('''LCS''') is a subsequence of maximum length common to two or more strings.

 

 

 

 

 

 

 

 

 

 

 

'''Background'''

 

 

 

This quadratic time dependency may become prohibitive, given very long input strings. Thus, heuristics are often favored over optimal Dynamic Programming solutions.

A, B are input strings of lengths m, n respectively

p is the length of the LCS

r is the magnitude of M

 

'''References'''

{{trans|Python}}

 

V lengths = [[0] * (b.len+1)] * (a.len+1)

L(x) a

 

print(lcs(‘1234’, ‘1224533324’))

 

{{out}}

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

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

{{trans|FreeBASIC}}

if length(a) = 0 or length(b) = 0 then return ""

if right(a, 1) = right(b, 1) then

print LCS("1234", "1224533324")

print LCS("thisisatest", "testing123testing")

 

 

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

=={{header|BQN}}==

It's easier and faster to get only the length of the longest common subsequence, using <code>LcsLen ← ¯1 ⊑ 0¨∘⊢ {𝕩⌈⌈`𝕨+»𝕩}˝ =⌜⟜⌽</code>. This function can be expanded by changing <code>⌈</code> to <code>⊣⍟(>○≠)</code> (choosing from two arguments one that has the greatest length), and replacing the empty length 0 with the empty string <code>""</code> in the right places.

Output:

"1234"

"thisisatest" LCS "testing123testing"

 

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

 

=={{header|C sharp|C#}}==

===With recursion===

 

namespace LCS

}

}

 

=={{header|C++}}==

'''Hunt and Szymanski algorithm'''

#include <string>

#include <memory> // for shared_ptr<>

#include <iostream>

#include <deque>

#include <algorithm> // for lower_bound()

#include <iterator> // for next() and prev()

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

 

// Return the LCS as a linked list of matched index pairs:

*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

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

:else (longest (lcs (cons x 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}}==

This solution is Brute force. It is slow

{{trans|Ruby}}

def lcs(a, b) do

lcs(to_charlist(a), to_charlist(b), []) |> to_string

 

IO.puts LCS.lcs("thisisatest", "testing123testing")

 

===Dynamic Programming===

{{trans|Erlang}}

def lcs_length(s,t), do: lcs_length(s,t,Map.new) |> elem(0)

 

IO.puts LCS.lcs("thisisatest","testing123testing")

 

{{out}}

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

 

Similar to the above, but without using the process dictionary:

-module(lcs).

 

end,

{LCS, CacheB}.

 

'''Output:'''

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

"tsitest"

 

=={{header|F Sharp|F#}}==

Copied and slightly adapted from OCaml (direct recursion)

 

let longest xs ys = if List.length xs > List.length ys then xs else ys

(lcs (split "thisisatest") (split "testing123testing"))))

0

 

=={{header|Factor}}==

{{out}}

<pre>

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

Dim As String x, y

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

Print LCS("1234", "1224533324")

Print LCS("thisisatest", "testing123testing")

 

 

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

 

const longest = (xs, ys) => (xs.length > ys.length) ? xs : ys;

 

 

return (x === y) ? (x + lcs(xs, ys)) : longest(lcs(xx, ys), lcs(xs, yy));

 

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

{{works with|Julia|0.6}}

 

"""

@time lcsrecursive("thisisatest", "testing123testing")

@show lcsdynamic("thisisatest", "testing123testing")

 

{{out}}

 

=={{header|Kotlin}}==

 

fun lcs(x: String, y: String): String {

val y = "testing123testing"

println(lcs(x, y))

 

{{out}}

 

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

 

=={{header|Mathematica}}/{{header|Wolfram Language}}==

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

 

===Recursion===

{{trans|Python}}

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

return ""

 

echo lcs("1234", "1224533324")

 

This recursive version is not efficient but the execution time can be greatly improved by using memoization.

===Dynamic Programming===

{{trans|Python}}

var ls = newSeq[seq[int]](a.len+1)

for i in 0 .. a.len:

 

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

my ($a, $b) = @_;

if (!length($a) || !length($b)) {

}

 

 

===Alternate letting regex do all the work===

use warnings;

 

print "lcs is ", lcs('thisisatest', 'testing123testing'), "\n";

{

my ($c, $d) = @_;

{

"$c\n$d" =~ join '.*', ('(.)') x $len, "\n", map "\\$_", 1 .. $len and

}

return '';

{{out}}

 

=={{header|Phix}}==

If you want this to work with (utf8) Unicode text, just chuck the inputs through utf8_to_utf32() first (and the output through utf32_to_utf8()).

<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>

<span style="color: #008080;">function</span> <span style="color: #000000;">lcs</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">a</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">b</span><span style="color: #0000FF;">)</span>

<span style="color: #0000FF;">?</span><span style="color: #000000;">lcs</span><span style="color: #0000FF;">(</span><span style="color: #000000;">a</span><span style="color: #0000FF;">,</span><span style="color: #000000;">b</span><span style="color: #0000FF;">)</span>

<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>

{{out}}

<pre>

===Alternate version===

same output

<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>

<span style="color: #008080;">function</span> <span style="color: #000000;">LCSLength</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">X</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">sequence</span> <span style="color: #000000;">Y</span><span style="color: #0000FF;">)</span>

<span style="color: #0000FF;">?</span><span style="color: #000000;">lcs</span><span style="color: #0000FF;">(</span><span style="color: #000000;">a</span><span style="color: #0000FF;">,</span><span style="color: #000000;">b</span><span style="color: #0000FF;">)</span>

<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>

 

=={{header|PicoLisp}}==

(when A

(conc

(commonSequences

(chop "thisisatest")

{{out}}

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

=={{header|PowerShell}}==

Returns a sequence (array) of a type:

function Get-Lcs ($ReferenceObject, $DifferenceObject)

{

$longestCommonSubsequence

}

Returns the character array as a string:

(Get-Lcs -ReferenceObject "thisisatest" -DifferenceObject "testing123testing") -join ""

{{Out}}

<pre>

</pre>

Returns an array of integers:

Get-Lcs -ReferenceObject @(1,2,3,4) -DifferenceObject @(1,2,2,4,5,3,3,3,2,4)

{{Out}}

<pre>

</pre>

Given two lists of objects, return the LCS of the ID property:

$list1

 

 

Get-Lcs -ReferenceObject $list1.ID -DifferenceObject $list2.ID

{{Out}}

<pre>

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

return str(lcs(xs, ys)) + x

else:

Test it:

 

===Dynamic Programming===

# generate matrix of length of longest common subsequence for substrings of both words

lengths = [[0] * (len(b)+1) for _ in range(len(a)+1)]

result += a[i-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>

{{works with|rakudo|2015-09-16}}

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

return "" unless $xstr && $ystr;

 

}

 

 

===Dynamic Programming===

{{trans|Java}}

sub lcs(Str $xstr, Str $ystr) {

my ($xlen, $ylen) = ($xstr, $ystr)>>.chars;

}

 

 

===Bit Vector===

Bit parallel dynamic programming with nearly linear complexity O(n). It is fast.

 

 

}

 

}

}

}

 

 

=={{header|ReasonML}}==

 

let longest = (xs, ys) =>

if (List.length(xs) > List.length(ys)) {

}

};

 

=={{header|REXX}}==

parse arg aaa bbb . /*obtain optional arguments from the CL*/

say 'string A =' aaa /*echo the string A to the screen. */

y= LCS( substr(a, 1, j - 1), b, 9)

if length(x)>length(y) then return x

{{out|output|text=&nbsp; when using the input of: &nbsp; &nbsp; <tt> 1234 &nbsp; 1224533324 </tt>}}

<pre>

 

=={{header|Ring}}==

see longest("1267834", "1224533324") + nl

lcs = x2

return lcs ok ok

Output:

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

 

=={{header|Rust}}==

Dynamic programming version:

use std::cmp;

 

let res = lcs("AGGTAB".to_string(), "GXTXAYB".to_string());

assert_eq!((4 as usize, "GTAB".to_string()), res);

 

=={{header|Scala}}==

{{works with|Scala 2.13}}

Using lazily evaluated lists:

def su = subsets(u).to(LazyList)

def sv = subsets(v).to(LazyList)

def subsets[T](u: IndexedSeq[T]): Iterator[IndexedSeq[T]] = {

u.indices.reverseIterator.flatMap{n => u.indices.combinations(n + 1).map(_.map(u))}

 

Using recursion:

case (a +: as, b +: bs) if a == b => a +: lcsRec(as, bs)

case (as, bs) if as.isEmpty || bs.isEmpty => IndexedSeq[T]()

val (s1, s2) = (lcsRec(a +: as, bs), lcsRec(as, b +: bs))

if(s1.length > s2.length) s1 else s2

 

{{out}}

{{works with|Scala 2.9.3}}

Recursive version:

case (_, Nil) => Nil

case (Nil, _) => Nil

}

}

 

The dynamic programming version:

 

val cache = scala.collection.mutable.Map.empty[(A1, A2), B]

def apply(x: A1, y: A2) = cache.getOrElseUpdate((x, y), f(x, y))

}

}

 

{{out}}

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:

It is interesting to note that x and y are computed in parallel, dividing work across threads repeatedly down through the recursion.

 

lcsBack(a(1), b(1)) :=

lcsBack(args[1], args[2]) when size(args) >=2

else

 

{{out}}

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

Swift 5.1

===Recursion===

if s1.count == 0 || s2.count == 0 {

return ""

return str1.count > str2.count ? str1 : str2

}

 

===Dynamic Programming===

var lens = Array(

repeating:Array(repeating: 0, count: s2.count + 1),

return String(returnStr.reversed())

 

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

}

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

{{trans|Kotlin}}

lcs = Fn.new { |x, y|

if (x.count == 0 || y.count == 0) return ""

var x = "thisisatest"

var y = "testing123testing"

 

{{out}}

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