Longest common subsequence: Difference between revisions

<langsyntaxhighlight lang="ada">with Ada.Text_IO; use Ada.Text_IO;

end Test_LCS;</langsyntaxhighlight>

<langsyntaxhighlight lang="ada">with Ada.Text_IO; use Ada.Text_IO;

end Test_LCS;</langsyntaxhighlight>

<langsyntaxhighlight lang="algol68">main:(

)</langsyntaxhighlight>

<langsyntaxhighlight APLlang="apl">lcs←{

}</langsyntaxhighlight>

<langsyntaxhighlight AutoHotkeylang="autohotkey">lcs(a,b) { ; Longest Common Subsequence of strings, using Dynamic Programming

}</langsyntaxhighlight>

<langsyntaxhighlight lang="qbasic">FUNCTION lcs$ (a$, b$)

END FUNCTION</langsyntaxhighlight>

<langsyntaxhighlight lang="bbcbasic"> PRINT FNlcs("1234", "1224533324")

= x$</langsyntaxhighlight>

<langsyntaxhighlight lang="bracmat"> ( LCS

& out$(max !max lcs !lcs);</langsyntaxhighlight>

<langsyntaxhighlight lang="c">#include <stringstdio.h>

#define MAX(Aa,B b) (((A)a >(B)) b ? (A)a : (B)b)

char *int lcs(const (char *a,const int n, char * b, int m, char **s) {

int lenai, =j, strlen(a)+1k, t;

int lenb*z = strlencalloc(b(n + 1) * (m + 1), sizeof (int));

intfor bufrlen(i = 400; i <= n; i++) {

char bufr c[40i], = &z[i *result (m + 1)];

intfor (i,j = 1; i <= n; i++) {

int mlc[i][j] = MAX(lengthsc[i+ - 1][j], lengthsc[i][j+ - 1]);

result*s = bufr+bufrlenmalloc(t);

i = lena if (a[i - 1; j] == lenbb[j - 1;])

while ( (i>0) && (j>0*s)[k] )= a[i - 1], i--, j--, {k--;

else if (lengthsc[i][j - 1] ==> lengthsc[i - 1][j]) i -= 1;

else if (lengths[i][j] == lengths[i][j-1]) j-= 1;

else {

free(la); free(lengthsc);

return strdupfree(resultz);

<langsyntaxhighlight lang="c">int main () {

printf("%s\n",char lcs("thisisatest",b[] = "testing123testing")); // tsitest

}</langsyntaxhighlight>

}</langsyntaxhighlight>

<langsyntaxhighlight Clojurelang="clojure">(defn longest [xs ys] (if (> (count xs) (count ys)) xs ys))

(cond

(or (= x nil) (= y nil) ) nil

:else (longest (lcs (cons x xs) ys) (lcs xs (cons y ys)))))))</lang>

<langsyntaxhighlight lang="coffeescript">

console.log lcs(s1, s2)</langsyntaxhighlight>

<langsyntaxhighlight lang="lisp">(defun longest-common-subsequence (array1 array2)

(values (coerce seq (type-of array1)) len)))))</langsyntaxhighlight>

<langsyntaxhighlight lang="lisp">(longest-common-subsequence "123456" "1a2b3c")</langsyntaxhighlight>

<langsyntaxhighlight lang="lisp">"123"

3</langsyntaxhighlight>

<langsyntaxhighlight lang="d">import std.stdio, std.array;

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

}</langsyntaxhighlight>

<langsyntaxhighlight lang="d">import std.stdio, std.algorithm, std.traits;

}</langsyntaxhighlight>

<langsyntaxhighlight lang="d">import std.stdio, std.algorithm, std.range, std.array, std.string, std.typecons;

}</langsyntaxhighlight>

<langsyntaxhighlight lang="dart">import 'dart:math';

<langsyntaxhighlight lang="egison">

<langsyntaxhighlight lang="egison">

<langsyntaxhighlight lang="erlang">

<langsyntaxhighlight lang="erlang">

<langsyntaxhighlight lang="fortran">program lcstest

end program lcstest</langsyntaxhighlight>

<langsyntaxhighlight lang="go">func lcs(a, b string) string {

}</langsyntaxhighlight>

<langsyntaxhighlight lang="go">func lcs(a, b string) string {

}</langsyntaxhighlight>

<langsyntaxhighlight lang="haskell">longest xs ys = if length xs > length ys then xs else ys

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

<langsyntaxhighlight lang="haskell">import qualified Data.MemoCombinators as M

mString = M.list M.char -- Chars, but you can specify any type you need for the memo</langsyntaxhighlight>

<langsyntaxhighlight lang="haskell">import Data.Array

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

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

"tsitest"</langsyntaxhighlight>

<langsyntaxhighlight lang="haskell">import Data.List

| otherwise = (a++d):[b]</langsyntaxhighlight>

<langsyntaxhighlight lang="haskell">import Data.Ord

main = print $ lcs "thisisatest" "testing123testing"</langsyntaxhighlight>

<langsyntaxhighlight Iconlang="icon">procedure main()

end</langsyntaxhighlight>

<langsyntaxhighlight lang="j">lcs=: dyad define

cullOne=: ({~[: <@<@< [: (i. 0:)1,[: *./[: |: 2>/\]) :: ]</langsyntaxhighlight>

<langsyntaxhighlight Jlang="j">mergeSq=: ;@}: ~.@, {.@;@{. ,&.> 3 {:: 4&{.

lcs=: [ {~ 0 {"1 ,&$ #: 0 ({:: (#~ [: (= >./) #@>)) 0 ({:: ,) common</langsyntaxhighlight>

<langsyntaxhighlight Jlang="j"> 'thisisatest' lcs 'testing123testing'

tsitest</langsyntaxhighlight>

<langsyntaxhighlight lang="j">longest=: ]`[@.(>&#)

lcs=: 0{:: [: ([: {.&> [: upd&.>/\.<"1@:,.)/ a:,.~a:,~=/{"1 a:,.<"0@[</langsyntaxhighlight>

<langsyntaxhighlight lang="j"> '1234' lcs '1224533324'

tsitest</langsyntaxhighlight>

<langsyntaxhighlight lang="j">lcs=:;(($:}.) longest }.@[ $: ])`({.@[,$:&}.)@.(=&{.)`((i.0)"_)@.(+.&(0=#))&((e.#[)&>/) ;~</langsyntaxhighlight>

<langsyntaxhighlight lang="java">public static String lcs(String a, String b){

}</langsyntaxhighlight>

<langsyntaxhighlight lang="java">public static String lcs(String a, String b) {

}</langsyntaxhighlight>

<langsyntaxhighlight lang="javascript">function lcs(a, b) {

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

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

if (a.length === 0 || b.length === 0) {

return ""'';

} else if (a.charAt(a.length - 1) === b.charAt(b.length - 1)) {

return lcs(aSub, bSub) + a.charAt(a.length - 1);

}</langsyntaxhighlight>

<langsyntaxhighlight lang="javascript">function lcs(x,y){

}</langsyntaxhighlight>

<langsyntaxhighlight lang="javascript"> var t=i;

if(t!==i){lcs.unshift(x.substring(i+1,t+1));}</langsyntaxhighlight>

This is aan bitheuristic harderalgorithm tothat understandwon'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;

<langsyntaxhighlight lang="javascript">function lcs_greedy(x,y){

var symbolsp1, =i, {}idx,

if(idx===n){p p1 = popsym(i0);}

function popsym(index) {

var s = x[index],

pos = symbols[s] + 1;

<langsyntaxhighlight lang="logo">to longest :s :t

end</langsyntaxhighlight>

<langsyntaxhighlight lang="lua">function LCS( a, b )

print( LCS( "thisisatest", "testing123testing" ) )</langsyntaxhighlight>

<langsyntaxhighlight M4lang="m4">define(`set2d',`define(`$1[$2][$3]',`$4')')

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

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

<langsyntaxhighlight Mathematicalang="mathematica">a = "thisisatest";

LongestCommonSequence[a, b]</langsyntaxhighlight>

<syntaxhighlight lang Mathematica="mathematica">tsitest</langsyntaxhighlight>

I added this note because the name of this article suggests LongestCommonSubsequence does the job, however LongestCommonSubsequenceLongestCommonSequence performs the puzzle-description.

=={{header|NimrodNim}}==

<langsyntaxhighlight nimrodlang="nim">proc lcs(x, y: string): string =

echo lcs("thisisatest", "testing123testing")</langsyntaxhighlight>

<langsyntaxhighlight nimrodlang="nim">proc lcs(a, b: string): string =

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

ls[i].newSeq (b.len+1)

echo lcs("thisisatest", "testing123testing")</langsyntaxhighlight>

<langsyntaxhighlight lang="ocaml">let longest xs ys = if List.length xs > List.length ys then xs else ys

longest (lcs a ys) (lcs xs b)</langsyntaxhighlight>

<langsyntaxhighlight lang="ocaml">let lcs xs' ys' =

a.(0).(0)</langsyntaxhighlight>

<langsyntaxhighlight lang="ocaml">let list_of_string str =

result</langsyntaxhighlight>

<langsyntaxhighlight lang="oz">declare

{System.showInfo {LCS "thisisatest" "testing123testing"}}</langsyntaxhighlight>

<langsyntaxhighlight lang="pascal">Program LongestCommonSubsequence(output);

end.</langsyntaxhighlight>

<syntaxhighlight lang ="perl">use Algorithm::Diff qw/sub LCSlcs /;{

my ?? $x ~ lcs($xsc, $ysd) = @_;

for my $len ( reverse 1 !! max({ $^a.chars. }, lcslength($xstr,c $ys), lcs($xs,&. $ystrd) );

C = while[[0 $x: !=J 0in &&1..N+1] $y !=: 0I in {1..N+1],

if X[I-1] == Y[J-1] $x--;then

}C[I,J] := C[I-1,J-1] + 1

C[I,J] := max([C[I,J-1], $y-C[I-;1,J]])

}end

<langsyntaxhighlight PicoLisplang="picolisp">(de commonSequences (A B)

(chop "testing123testing") ) )</langsyntaxhighlight>

<langsyntaxhighlight Prologlang="prolog">test :-

((Length1 > Length2) -> Longest = L1; Longest = L2).</langsyntaxhighlight>

<langsyntaxhighlight Prologlang="prolog">%declare that we will add lcs_db facts during runtime

((Length1 > Length2) -> Longest = L1; Longest = L2).</langsyntaxhighlight>

<langsyntaxhighlight Prologlang="prolog">?- time(lcs("beginning-middle-ending","beginning-diddle-dum-ending", Lcs)),writef('%s', [Lcs]).

beginning-iddle-ending</langsyntaxhighlight>

<langsyntaxhighlight Prologlang="prolog">?- time(lcs("beginning-middle-ending","beginning-diddle-dum-ending", Lcs)),writef('%s', [Lcs]).

beginning-iddle-ending</langsyntaxhighlight>

<langsyntaxhighlight PureBasiclang="purebasic">Procedure.s lcs(a$, b$)

PrintN("Press any key to exit"): Repeat: Until Inkey() <> ""</langsyntaxhighlight>

The simplest way is to use [http://mlpy.sourceforge.net/docs/3.5/lcs.html| LCS within mlpy package]

<langsyntaxhighlight lang="python">def lcs(xstr, ystr):

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

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

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

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

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

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

# read thea substring out from the matrix

result = ""''

x, yj = len(a), len(b)

whilefor xi !=in 0range(1, and y != 0len(a)+1):

if lengths[xi][yj] =!= lengths[xi-1][yj]:

xresult -+= a[i-1]

<langsyntaxhighlight lang="racket">#lang racket

(lcs "thisisatest" "testing123testing")</langsyntaxhighlight>

<langsyntaxhighlight lang="rexx">/*REXX program to testtests the LCS (Longest Common Subsequence) subroutine. */

parse arg aaa bbb . /*getobtain twooptional arguments (strings). from the CL*/

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

say 'string B = ' bbb /*echo string " " " B to screen. " " " */

say ' LCS = 'lcs LCS(aaa, bbb) /*tell the Longest Common Sequence. */

exit /*stick a fork in it, we're all done. */

lcsLCS: procedure; parse arg a,b,z /*Longest Common Subsequence. */

/*reduce recursions, removes the */

/*chars in A ¬ in B, & vice-versa and vice─versa.*/

if z=='' then return lcsLCS( lcsLCS(a,b,0), lcsLCS(b,a,0), 9) /*Is Z null? Do recurse. */

j= length(a)

if z==0 then do /*a special invocation: shrink Z. */

do j=1 for j; _= substr(a, j, 1)

if pos(_, b)\==0 then z= z || _

end /*j*/

return substr(z, 2)

end

k= length(b)

if j==0 | k==0 then return '' /*EitherIs either string null? Bupkis. */

_= substr(a, j, 1)

if _==substr(b, k, 1) then return lcsLCS( substr(a, 1, j - 1), substr(b, 1, k - 1), 9)_

x=lcs LCS(a, substr(b, 1, k - 1), 9)

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

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

return y</langsyntaxhighlight>

{{out|Outputoutput|text=&nbsp; withwhen using the input “of: &nbsp; &nbsp; <tt> 1234 &nbsp; 1224533324 </tt>”}}

string A = 1234

string B = 1224533324

LCS = 1234

{{out|Outputoutput|text=&nbsp; withwhen using the input “of: &nbsp; &nbsp; <tt> thisisatest &nbsp; testing123testing </tt>”}}

string A = thisisatest

string B = testing123testing

LCS = tsitest

<langsyntaxhighlight lang="ruby">=begin

return "" if xstr.empty? || ystr.empty?

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

if x == y

x + lcs(xs, ys)

else

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

end

end</langsyntaxhighlight>

===Dynamic programming, walker class===

<langsyntaxhighlight lang="ruby">class LcsWalkerLCS

def initialize(matrix); @ma, @i, @j = matrix, 0, 0; end b)

def backstepbacktrack2

end</lang>

<langsyntaxhighlight lang="runbasic">a$ = "aebdaef"

END FUNCTION</langsyntaxhighlight><pre>aba</pre>

=={{header|ScalaRust}}==

val y = lcsrassert_eq!(a.substring(0string1_chars[x-1],a.size string2_chars[y-1]),b);

if (x.size >let char y.size)= string1_chars[x else- y1];

case (a +: as, forb (i+: <-bs) 0if untila == b => a.size +: lcsRec(as, bs)

case (a +: as, b +: if (a(ibs) == b(j))>

val (s1, s2) = lengths(i+1)lcsRec(ja +1): =as, lengths(ibs), lcsRec(j)as, b +: 1bs))

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

case (_, Nil) => else {Nil

case (Nil, assert(a(x-1_) ==> b(y-1))Nil

case (x :: xs, y :: ys) if sbx +== a(y => x-1 :: lcs(xs, ys)

case (x :: xs, y :: ys) x -=> 1{

(lcs(x :: xs, ys), lcs(xs, y -=:: ys)) match 1{

} whilecase (x!=0xs, ys) && y!=0)> ys

}

case (x :: xs, y :: ys) if "lcsd(\""+p._1+"\",\""+p._2+"\")x == \""+s+"\"y => x :: lcsM("+t+"xs, secys)"}

lcsr("","x") = "" (0 sec)}

lcsd scala> lcsM("thisiaatest".toList, "testing123testing".toList) = "tsitest" (0 sec).mkString

<langsyntaxhighlight lang="scheme">

<langsyntaxhighlight lang="scheme">

<langsyntaxhighlight lang="seed7">$ include "seed7_05.s7i";

end func;</langsyntaxhighlight>

<langsyntaxhighlight lang="setl"> op .longest(a, b);

end lcs;</langsyntaxhighlight>

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

].</langsyntaxhighlight>

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

].</langsyntaxhighlight>

<langsyntaxhighlight lang="tcl">proc r_lcs {a b} {

}</langsyntaxhighlight>

<langsyntaxhighlight lang="tcl">package require Tcl 8.5

while {$x > 0 && $xy > 0} {

}</langsyntaxhighlight>

<langsyntaxhighlight lang="tcl">% time {d_lcs thisisatest testing123testing} 10

1275566.8 microseconds per iteration</langsyntaxhighlight>

<langsyntaxhighlight Ursalalang="ursala">#import std

lcs = ~&alrB^& ~&E?abh/~&alh2fabt2RC @faltPrXlrtPXXPW leql?/~&r ~&l</langsyntaxhighlight>

<langsyntaxhighlight Ursalalang="ursala">#cast %s

example = lcs('thisisatest','testing123testing')</langsyntaxhighlight>

<langsyntaxhighlight lang="zkl">fcn lcs(a,b){

}</langsyntaxhighlight>