Longest common subsequence: Difference between revisions

Let ''A'' ≡ ''A''[0]… ''A''[m - 1] and ''B'' ≡ ''B''[0]… ''B''[n - 1], m < n be strings drawn from an alphabet Σ of size s, containing every distinct symbol in A + B.

 

 

Define a ''non-strict'' [https://en.wikipedia.org/wiki/Product_order product-order] (≤) over ordered pairs, such that (i1, j1) ≤ (i2, j2) ⇔ i1 ≤ i2 and j1 ≤ j2. We define (≥) similarly.

 

 

 

 

 

 

 

'''Background'''

 

 

The divide-and-conquer approach of [Hirschberg 1975] limits the space required to O(''n''). However, this approach requires O(''m*n'') time even in the best case.

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

p is the length of the LCS

r is the magnitude of M

s is the magnitude of the alphabet Σ of distinct symbols in A + B

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

{{trans|Python}}

ls: new array.of: @[inc size a, inc size b] 0

 

print lcs "1234" "1224533324"

 

{{out}}

{{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 unordered_map<char, INDEXES> CHAR_TO_INDEXES_MAP;

typedef deque<INDEXES*> MATCHES;

 

auto traceLCS = pairs != nullptr;

PAIRS chains;

 

//

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

//

uint32_t index1 = 0;

for (const auto& it1 : indexesOf2MatchedByIndex1) {

 

 

 

}

}

 

index1++;

if (traceLCS) {

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

// Reverse longest chain

*pairs = Pair::Reverse(last);

}

 

return length;

}

 

//

// Match() avoids m*n comparisons by using CHAR_TO_INDEXES_MAP to

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

//

const string& s1, const string& s2) {

uint32_t index = 0;

}

 

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

string buffer;

 

public:

CHAR_TO_INDEXES_MAP indexesOf2MatchedByChar;

MATCHES indexesOf2MatchedByIndex1; // holds references into indexesOf2MatchedByChar

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

[C, _Len] = lcs_length(X,Y),

V = backTrace(C,X,Y,X.length+1,Y.length+1).

V = backTrace(C, X, Y, I-1, J)

end

 

lcs_rule(A, B) = "", (A == ""; B == "") => true.

lcs_rule(A, B) = [A[1]] ++ lcs_rule(butfirst(A), butfirst(B)), A[1] == B[1] => true.

% butfirst (everything except first element)

 

 

<pre>fun = lcs_wiki

[thisisatest,testing123testing] : tsitest

 

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