Longest common subsequence: Difference between revisions
m
syntax highlighting fixup automation
SqrtNegInf (talk | contribs) m (→Bit Vector: fiddle with sigils and layout) |
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
||
Line 111:
{{trans|Python}}
<
V lengths = [[0] * (b.len+1)] * (a.len+1)
L(x) a
Line 130:
print(lcs(‘1234’, ‘1224533324’))
print(lcs(‘thisisatest’, ‘testing123testing’))</
{{out}}
Line 140:
=={{header|Ada}}==
Using recursion:
<
procedure Test_LCS is
Line 164:
begin
Put_Line (LCS ("thisisatest", "testing123testing"));
end Test_LCS;</
{{out}}
<pre>
Line 170:
</pre>
Non-recursive solution:
<
procedure Test_LCS is
Line 214:
begin
Put_Line (LCS ("thisisatest", "testing123testing"));
end Test_LCS;</
{{out}}
<pre>
Line 225:
{{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
Line 239:
END # lcs #;
print((lcs ("thisisatest", "testing123testing"), new line))
)</
{{out}}
<pre>
Line 247:
=={{header|APL}}==
{{works with|Dyalog APL}}
<
⎕IO←0
betterof←{⊃(</+/¨⍺ ⍵)⌽⍺ ⍵} ⍝ better of 2 selections
Line 267:
this ∇ 1↓[1]⍵ ⍝ keep looking
}sstt
}</
=={{header|Arturo}}==
{{trans|Python}}
<
ls: new array.of: @[inc size a, inc size b] 0
Line 297:
print lcs "1234" "1224533324"
print lcs "thisisatest" "testing123testing"</
{{out}}
Line 307:
{{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
Line 334:
}
Return t
}</
=={{header|BASIC}}==
{{works with|QuickBasic|4.5}}
{{trans|Java}}
<
IF LEN(a$) = 0 OR LEN(b$) = 0 THEN
lcs$ = ""
Line 353:
END IF
END IF
END FUNCTION</
=={{header|BASIC256}}==
{{trans|FreeBASIC}}
<
if length(a) = 0 or length(b) = 0 then return ""
if right(a, 1) = right(b, 1) then
Line 371:
print LCS("1234", "1224533324")
print LCS("thisisatest", "testing123testing")
end</
=={{header|BBC BASIC}}==
This makes heavy use of BBC BASIC's shortcut '''LEFT$(a$)''' and '''RIGHT$(a$)''' functions.
<
PRINT FNlcs("thisisatest", "testing123testing")
END
Line 387:
y$ = FNlcs(LEFT$(a$), b$)
IF LEN(y$) > LEN(x$) SWAP x$,y$
= x$</
'''Output:'''
<pre>
Line 396:
=={{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"
"tsitest"</
=={{header|Bracmat}}==
<
= A a ta B b tb prefix
. !arg:(?prefix.@(?A:%?a ?ta).@(?B:%?b ?tb))
Line 416:
& :?lcs
& LCS$(.thisisatest.testing123testing)
& out$(max !max lcs !lcs);</
{{out}}
<pre>max 7 lcs t s i t e s t</pre>
=={{header|C}}==
<
#include <stdlib.h>
Line 457:
return t;
}
</syntaxhighlight>
Testing
<
char a[] = "thisisatest";
char b[] = "testing123testing";
Line 468:
printf("%.*s\n", t, s); // tsitest
return 0;
}</
=={{header|C sharp|C#}}==
===With recursion===
<
namespace LCS
Line 504:
}
}
}</
=={{header|C++}}==
'''Hunt and Szymanski algorithm'''
<
#include <string>
#include <memory> // for shared_ptr<>
Line 663:
return Select(pairs, length, false, s1, s2);
}
};</
'''Example''':
<
auto s = lcs.Correspondence(s1, s2);
cout << s << endl;</
=={{header|Clojure}}==
Based on algorithm from Wikipedia.
<
(def lcs
Line 680:
(= x y) (cons x (lcs xs ys))
:else (longest (lcs (cons x xs) ys)
(lcs xs (cons y ys)))))))</
=={{header|CoffeeScript}}==
<
lcs = (s1, s2) ->
len1 = s1.length
Line 714:
s1 = "thisisatest"
s2 = "testing123testing"
console.log lcs(s1, s2)</
=={{header|Common Lisp}}==
Here's a memoizing/dynamic-programming solution that uses an <var>n × 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))
Line 745:
b)))))))))
(destructuring-bind (seq len) (lcs 0 0)
(values (coerce seq (type-of array1)) len)))))</
For example,
<
produces the two values
<
3</
===An alternative adopted from Clojure===
Line 760:
Here is another version with its own memoization macro:
<
(let ((hash-name (gensym)))
`(let ((,hash-name (make-hash-table :test 'equal)))
Line 773:
((equal (car xs) (car ys)) (cons (car xs) (lcs (cdr xs) (cdr ys))))
(t (longer (lcs (cdr xs) ys)
(lcs xs (cdr ys)))))))</
When we test it, we get:
<
"tsitest"</
=={{header|D}}==
Line 785:
===Recursive version===
<
T[] lcs(T)(in T[] a, in T[] b) pure nothrow @safe {
Line 797:
void main() {
lcs("thisisatest", "testing123testing").writeln;
}</
{{out}}
<pre>tsitest</pre>
Line 803:
===Faster dynamic programming version===
The output is the same.
<
T[] lcs(T)(in T[] a, in T[] b) pure /*nothrow*/ {
Line 832:
void main() {
lcs("thisisatest", "testing123testing").writeln;
}</
===Hirschberg algorithm version===
Line 841:
Adapted from Python code: http://wordaligned.org/articles/longest-common-subsequence
<
uint[] lensLCS(R)(R xs, R ys) pure nothrow @safe {
Line 901:
void main() {
lcsString("thisisatest", "testing123testing").writeln;
}</
=={{header|Dart}}==
<
String lcsRecursion(String a, String b) {
Line 971:
print("lcsRecursion('x', 'x') = ${lcsRecursion('x', 'x')}");
}
</syntaxhighlight>
{{out}}
<pre>lcsDynamic('1234', '1224533324') = 1234
Line 985:
=={{header|Egison}}==
<
(define $common-seqs
(lambda [$xs $ys]
Line 994:
(define $lcs (compose common-seqs rac))
</syntaxhighlight>
'''Output:'''
<
> (lcs "thisisatest" "testing123testing"))
"tsitest"
</syntaxhighlight>
=={{header|Elixir}}==
Line 1,006:
This solution is Brute force. It is slow
{{trans|Ruby}}
<
def lcs(a, b) do
lcs(to_charlist(a), to_charlist(b), []) |> to_string
Line 1,019:
IO.puts LCS.lcs("thisisatest", "testing123testing")
IO.puts LCS.lcs('1234','1224533324')</
===Dynamic Programming===
{{trans|Erlang}}
<
def lcs_length(s,t), do: lcs_length(s,t,Map.new) |> elem(0)
Line 1,062:
IO.puts LCS.lcs("thisisatest","testing123testing")
IO.puts LCS.lcs("1234","1224533324")</
{{out}}
Line 1,073:
=={{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).
Line 1,115:
lcs(ST,T,Cache,Acc)
end.
</syntaxhighlight>
'''Output:'''
<
77> lcs:lcs("thisisatest","testing123testing").
"tsitest"
78> lcs:lcs("1234","1224533324").
"1234"
</syntaxhighlight>
We can also use the process dictionary to memoize the recursive implementation:
<
lcs(Xs0, Ys0) ->
CacheKey = {lcs_cache, Xs0, Ys0},
Line 1,150:
Result
end.
</syntaxhighlight>
Similar to the above, but without using the process dictionary:
<
-module(lcs).
Line 1,193:
end,
{LCS, CacheB}.
</syntaxhighlight>
'''Output:'''
<
48> lcs:lcs("thisisatest", "testing123testing").
"tsitest"
</syntaxhighlight>
=={{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
Line 1,223:
(lcs (split "thisisatest") (split "testing123testing"))))
0
</syntaxhighlight>
=={{header|Factor}}==
<
"thisisatest" "testing123testing" lcs print</
{{out}}
<pre>
Line 1,237:
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
Line 1,274:
end function lcs
end program lcstest</
=={{header|FreeBASIC}}==
<
Dim As String x, y
If Len(a) = 0 Or Len(b) = 0 Then
Line 1,293:
Print LCS("1234", "1224533324")
Print LCS("thisisatest", "testing123testing")
Sleep</
Line 1,300:
===Recursion===
Brute force
<
aLen := len(a)
bLen := len(b)
Line 1,314:
}
return y
}</
===Dynamic Programming===
<
arunes := []rune(a)
brunes := []rune(b)
Line 1,358:
}
return string(s)
}</
=={{header|Groovy}}==
Recursive solution:
<
if (xstr == "" || ystr == "") {
return "";
Line 1,384:
println(lcs("1234", "1224533324"));
println(lcs("thisisatest", "testing123testing"));</
{{out}}
<pre>1234
Line 1,393:
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 [] _ = []
Line 1,399:
lcs (x:xs) (y:ys)
| x == y = x : lcs xs ys
| otherwise = longest (lcs (x:xs) ys) (lcs xs (y:ys))</
A Memoized version of the naive algorithm.
<
lcs = memoize lcsm
Line 1,415:
maxl x y = if length x > length y then x else y
memoize = M.memo2 mString mString
mString = M.list M.char -- Chars, but you can specify any type you need for the memo</
Memoization (aka dynamic programming) of that uses ''zip'' to make both the index and the character available:
<
lcs xs ys = a!(0,0) where
Line 1,430:
f x y i j
| x == y = x : a!(i+1,j+1)
| otherwise = longest (a!(i,j+1)) (a!(i+1,j))</
All 3 solutions work of course not only with strings, but also with any other list. Example:
<
"tsitest"</
The dynamic programming version without using arrays:
<
longest xs ys = if length xs > length ys then xs else ys
Line 1,444:
f [a,b] [c,d]
| null a = longest b c: [b]
| otherwise = (a++d):[b]</
Simple and slow solution:
<
import Data.List
Line 1,455:
lcs xs ys = maximumBy (comparing length) $ intersect (subsequences xs) (subsequences ys)
main = print $ lcs "thisisatest" "testing123testing"</
{{out}}
<pre>"tsitest"</pre>
Line 1,464:
{{libheader|Icon Programming Library}} [http://www.cs.arizona.edu/icon/library/src/procs/strings.icn Uses deletec from strings]
<
LCSTEST("thisisatest","testing123testing")
LCSTEST("","x")
Line 1,499:
return if *(x := lcs(a,b[1:-1])) > *(y := lcs(a[1:-1],b)) then x else y # divide, discard, and keep longest
end</
{{out}}
<pre>lcs( "thisisatest", "testing123testing" ) = "tsitest"
Line 1,507:
=={{header|J}}==
<
|.x{~ 0{"1 cullOne^:_ (\: +/"1)(\:{."1) 4$.$. x =/ y
)
cullOne=: ({~[: <@<@< [: (i. 0:)1,[: *./[: |: 2>/\]) :: ]</
Here's [[Longest_common_subsequence/J|another approach]]:
<
common=: 2 2 <@mergeSq@,;.3^:_ [: (<@#&.> i.@$) =/
lcs=: [ {~ 0 {"1 ,&$ #: 0 ({:: (#~ [: (= >./) #@>)) 0 ({:: ,) common</
Example use (works with either definition of lcs):
<
tsitest</
'''Dynamic programming version'''
<
upd=:{:@[,~ ({.@[ ,&.> {:@])`({:@[ longest&.> {.@])@.(0 = #&>@{.@[)
lcs=: 0{:: [: ([: {.&> [: upd&.>/\.<"1@:,.)/ a:,.~a:,~=/{"1 a:,.<"0@[</
'''Output:'''
<
1234
'thisisatest' lcs 'testing123testing'
tsitest</
'''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();
Line 1,554:
return (x.length() > y.length()) ? x : y;
}
}</
===Dynamic Programming===
<
int[][] lengths = new int[a.length()+1][b.length()+1];
Line 1,587:
return sb.reverse().toString();
}</
=={{header|JavaScript}}==
Line 1,593:
{{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);
Line 1,606:
return (x.length > y.length) ? x : y;
}
}</
ES6 recursive implementation
<
const longest = (xs, ys) => (xs.length > ys.length) ? xs : ys;
Line 1,620:
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=[],
Line 1,659:
}
return lcs.join('');
}</
'''BUG note: In line 6, m and n are not yet initialized, and so x and y are never swapped.'''
Line 1,665:
The final loop can be modified to concatenate maximal common substrings rather than individual characters:
<
while(i>-1&&j>-1){
switch(c[i][j]){
Line 1,679:
}
}
if(t!==i){lcs.unshift(x.substring(i+1,t+1));}</
===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 = {},
Line 1,724:
return pos;
}
}</
Note that it won't return the correct answer for all inputs. For example: <
=={{header|jq}}==
Naive recursive version:
<
if (xstr == "" or ystr == "") then ""
else
Line 1,742:
| if ($one|length) > ($two|length) then $one else $two end
end
end;</
Example:
<
lcs("thisisatest"; "testing123testing")</
Output:<
# jq -n -f lcs-recursive.jq
"1234"
"tsitest"</
=={{header|Julia}}==
{{works with|Julia|0.6}}
<
"""
Line 1,810:
@time lcsrecursive("thisisatest", "testing123testing")
@show lcsdynamic("thisisatest", "testing123testing")
@time lcsdynamic("thisisatest", "testing123testing")</
{{out}}
Line 1,819:
=={{header|Kotlin}}==
<
fun lcs(x: String, y: String): String {
Line 1,835:
val y = "testing123testing"
println(lcs(x, y))
}</
{{out}}
Line 1,843:
=={{header|Liberty BASIC}}==
<syntaxhighlight lang="lb">
'variation of BASIC example
w$="aebdef"
Line 1,875:
END IF
END FUNCTION
</syntaxhighlight>
=={{header|Logo}}==
This implementation works on both words and lists.
<
output ifelse greater? count :s count :t [:s] [:t]
end
Line 1,887:
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</
=={{header|Lua}}==
<
if #a == 0 or #b == 0 then
return ""
Line 1,907:
end
print( LCS( "thisisatest", "testing123testing" ) )</
=={{header|M4}}==
<
define(`get2d',`defn($1[$2][$3])')
define(`tryboth',
Line 1,930:
lcs(`1234',`1224533324')
lcs(`thisisatest',`testing123testing')</
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}}==
<syntaxhighlight lang="maple">
> StringTools:-LongestCommonSubSequence( "thisisatest", "testing123testing" );
"tsitest"
</syntaxhighlight>
=={{header|Mathematica}}/{{header|Wolfram Language}}==
A built-in function can do this for us:
<
b = "testing123testing";
LongestCommonSequence[a, b]</
gives:
<syntaxhighlight lang
Note that Mathematica also has a built-in function called LongestCommonSubsequence[a,b]:
Line 1,961:
===Recursion===
{{trans|Python}}
<
if x == "" or y == "":
return ""
Line 1,973:
echo lcs("1234", "1224533324")
echo lcs("thisisatest", "testing123testing")</
This recursive version is not efficient but the execution time can be greatly improved by using memoization.
Line 1,979:
===Dynamic Programming===
{{trans|Python}}
<
var ls = newSeq[seq[int]](a.len+1)
for i in 0 .. a.len:
Line 2,006:
echo lcs("1234", "1224533324")
echo lcs("thisisatest", "testing123testing")</
=={{header|OCaml}}==
===Recursion===
from Haskell
<
let rec lcs a b = match a, b with
Line 2,020:
x :: lcs xs ys
else
longest (lcs a ys) (lcs xs b)</
===Memoized recursion===
<
let lcs xs ys =
let cache = Hashtbl.create 16 in
Line 2,043:
result
in
lcs xs ys</
===Dynamic programming===
<
let xs = Array.of_list xs'
and ys = Array.of_list ys' in
Line 2,060:
done
done;
a.(0).(0)</
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)
Line 2,072:
let result = String.create (List.length lst) in
ignore (List.fold_left (fun i x -> result.[i] <- x; i+1) 0 lst);
result</
Both solutions work. Example:
Line 2,085:
Recursive solution:
<
fun {LCS Xs Ys}
case [Xs Ys]
Line 2,099:
end
in
{System.showInfo {LCS "thisisatest" "testing123testing"}}</
=={{header|Pascal}}==
{{trans|Fortran}}
<
function lcs(a, b: string): string;
Line 2,136:
s2 := '1224533324';
writeln (lcs(s1, s2));
end.</
{{out}}
<pre>:> ./LongestCommonSequence
Line 2,144:
=={{header|Perl}}==
<
my ($a, $b) = @_;
if (!length($a) || !length($b)) {
Line 2,157:
}
print lcs("thisisatest", "testing123testing") . "\n";</
===Alternate letting regex do all the work===
<
use strict; # https://rosettacode.org/wiki/Longest_common_subsequence
Line 2,176:
}
return '';
}</
{{out}}
lcs is tsitest
Line 2,182:
=={{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>
Line 2,204:
<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>
Line 2,212:
===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>
Line 2,252:
<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}}==
===Wikipedia algorithm===
With some added trickery for a 1-based language.
<
[C, _Len] = lcs_length(X,Y),
V = backTrace(C,X,Y,X.length+1,Y.length+1).
Line 2,285:
V = backTrace(C, X, Y, I-1, J)
end
end.</
===Rule-based===
{{trans|SETL}}
<
lcs_rule(A, B) = "", (A == ""; B == "") => true.
lcs_rule(A, B) = [A[1]] ++ lcs_rule(butfirst(A), butfirst(B)), A[1] == B[1] => true.
Line 2,298:
% butfirst (everything except first element)
butfirst(A) = [A[I] : I in 2..A.length].</
===Test===
<
Tests = [["thisisatest","testing123testing"],
["XMJYAUZ", "MZJAWXU"],
Line 2,317:
end,
nl.</
{{out}}
Line 2,333:
=={{header|PicoLisp}}==
<
(when A
(conc
Line 2,344:
(commonSequences
(chop "thisisatest")
(chop "testing123testing") ) )</
{{out}}
<pre>-> ("t" "s" "i" "t" "e" "s" "t")</pre>
Line 2,350:
=={{header|PowerShell}}==
Returns a sequence (array) of a type:
<syntaxhighlight lang="powershell">
function Get-Lcs ($ReferenceObject, $DifferenceObject)
{
Line 2,398:
$longestCommonSubsequence
}
</syntaxhighlight>
Returns the character array as a string:
<syntaxhighlight lang="powershell">
(Get-Lcs -ReferenceObject "thisisatest" -DifferenceObject "testing123testing") -join ""
</syntaxhighlight>
{{Out}}
<pre>
Line 2,408:
</pre>
Returns an array of integers:
<syntaxhighlight lang="powershell">
Get-Lcs -ReferenceObject @(1,2,3,4) -DifferenceObject @(1,2,2,4,5,3,3,3,2,4)
</syntaxhighlight>
{{Out}}
<pre>
Line 2,419:
</pre>
Given two lists of objects, return the LCS of the ID property:
<syntaxhighlight lang="powershell">
$list1
Line 2,445:
Get-Lcs -ReferenceObject $list1.ID -DifferenceObject $list2.ID
</syntaxhighlight>
{{Out}}
<pre>
Line 2,458:
===Recursive Version===
First version:
<
time(lcs("thisisatest", "testing123testing", Lcs)),
writef('%s',[Lcs]).
Line 2,477:
length(L1,Length1),
length(L2,Length2),
((Length1 > Length2) -> Longest = L1; Longest = L2).</
Second version, with memoization:
<
:- dynamic lcs_db/3.
Line 2,507:
length(L1,Length1),
length(L2,Length2),
((Length1 > Length2) -> Longest = L1; Longest = L2).</
{{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)
beginning-iddle-ending</
Second version which is much faster :
<
% 2,376 inferences, 0.010 CPU in 0.003 seconds (300% CPU, 237600 Lips)
beginning-iddle-ending</
=={{header|PureBasic}}==
{{trans|Basic}}
<
Protected x$ , lcs$
If Len(a$) = 0 Or Len(b$) = 0
Line 2,540:
OpenConsole()
PrintN( lcs("thisisatest", "testing123testing"))
PrintN("Press any key to exit"): Repeat: Until Inkey() <> ""</
=={{header|Python}}==
Line 2,547:
===Recursion===
This solution is similar to the Haskell one. It is slow.
<
"""
>>> lcs('thisisatest', 'testing123testing')
Line 2,558:
return str(lcs(xs, ys)) + x
else:
return max(lcs(xstr, ys), lcs(xs, ystr), key=len)</
Test it:
<
import doctest; doctest.testmod()</
===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)]
Line 2,581:
result += a[i-1]
return result</
=={{header|Racket}}==
<
(define (longest xs ys)
(if (> (length xs) (length ys))
Line 2,609:
(list->string (lcs/list (string->list sx) (string->list sy))))
(lcs "thisisatest" "testing123testing")</
{{out}}
<pre>"tsitest"></pre>
Line 2,618:
{{works with|rakudo|2015-09-16}}
This solution is similar to the Haskell one. It is slow.
<syntaxhighlight lang="raku"
return "" unless $xstr && $ystr;
Line 2,627:
}
say lcs("thisisatest", "testing123testing");</
===Dynamic Programming===
{{trans|Java}}
<syntaxhighlight lang="raku" line>
sub lcs(Str $xstr, Str $ystr) {
my ($xlen, $ylen) = ($xstr, $ystr)>>.chars;
Line 2,662:
}
say lcs("thisisatest", "testing123testing");</
===Bit Vector===
Bit parallel dynamic programming with nearly linear complexity O(n). It is fast.
<syntaxhighlight lang="raku"
my (@a, @b) := ($xstr, $ystr)».comb;
my (%positions, @Vs, $lcs);
Line 2,689:
}
say lcs("thisisatest", "testing123testing");</
=={{header|ReasonML}}==
<
let longest = (xs, ys) =>
if (List.length(xs) > List.length(ys)) {
Line 2,712:
}
};
</syntaxhighlight>
=={{header|REXX}}==
<
parse arg aaa bbb . /*obtain optional arguments from the CL*/
say 'string A =' aaa /*echo the string A to the screen. */
Line 2,740:
y= LCS( substr(a, 1, j - 1), b, 9)
if length(x)>length(y) then return x
return y</
{{out|output|text= when using the input of: <tt> 1234 1224533324 </tt>}}
<pre>
Line 2,755:
=={{header|Ring}}==
<
see longest("1267834", "1224533324") + nl
Line 2,772:
lcs = x2
return lcs ok ok
</syntaxhighlight>
Output:
<pre>
Line 2,782:
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"
Line 2,795:
[lcs(xstr, ys), lcs(xs, ystr)].max_by {|x| x.size}
end
end</
===Dynamic programming===
Line 2,802:
Walker class for the LCS matrix:
<
SELF, LEFT, UP, DIAG = [0,0], [0,-1], [-1,0], [-1,-1]
Line 2,868:
puts lcs('thisisatest', 'testing123testing')
puts lcs("rosettacode", "raisethysword")
end</
{{out}}
Line 2,878:
=={{header|Run BASIC}}==
<
b$ = "cacbac"
print lcs$(a$,b$)
Line 2,904:
END IF
[ext]
END FUNCTION</
=={{header|Rust}}==
Dynamic programming version:
<
use std::cmp;
Line 2,964:
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)
Line 2,980:
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]()
Line 2,989:
val (s1, s2) = (lcsRec(a +: as, bs), lcsRec(as, b +: bs))
if(s1.length > s2.length) s1 else s2
}</
{{out}}
Line 2,999:
{{works with|Scala 2.9.3}}
Recursive version:
<
case (_, Nil) => Nil
case (Nil, _) => Nil
Line 3,009:
}
}
}</
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))
Line 3,028:
}
}
}</
{{out}}
Line 3,038:
Port from Clojure.
<
;; using srfi-69
(define (memoize proc)
Line 3,068:
'()))
'()))))
</syntaxhighlight>
Testing:
<
(test-group
Line 3,085:
(lcs '(a b d e f g h i j)
'(A b c d e f F a g h j))))
</syntaxhighlight>
=={{header|Seed7}}==
<
const func string: lcs (in string: a, in string: b) is func
Line 3,116:
writeln(lcs("thisisatest", "testing123testing"));
writeln(lcs("1234", "1224533324"));
end func;</
Output:
Line 3,129:
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)) :=
Line 3,150:
lcsBack(args[1], args[2]) when size(args) >=2
else
lcsBack("thisisatest", "testing123testing");</
{{out}}
Line 3,159:
=={{header|SETL}}==
Recursive; Also works on tuples (vectors)
<
return if #a > #b then a else b end;
end .longest;
Line 3,171:
return lcs(a(2..), b) .longest lcs(a, b(2..));
end;
end lcs;</
=={{header|Sidef}}==
<
xstr.is_empty && return xstr;
Line 3,189:
}
say lcs("thisisatest", "testing123testing");</
{{out}}
<pre>
Line 3,199:
===Recursion===
{{trans|Java}}
<
[
s1 isEmpty \/ s2 isEmpty ifTrue: [^ {}].
Line 3,208:
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).
Line 3,234:
index2: index2 - 1]]
] writingAs: s1) reverse
].</
=={{header|Swift}}==
Swift 5.1
===Recursion===
<
if s1.count == 0 || s2.count == 0 {
return ""
Line 3,251:
return str1.count > str2.count ? str1 : str2
}
}</
===Dynamic Programming===
<
var lens = Array(
repeating:Array(repeating: 0, count: s2.count + 1),
Line 3,286:
return String(returnStr.reversed())
}</
=={{header|Tcl}}==
===Recursive===
{{trans|Java}}
<
if {$a eq "" || $b eq ""} {return ""}
set a_ [string range $a 1 end]
Line 3,302:
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::-
Line 3,344:
}
return [string reverse $result]
}</
===Performance Comparison===
<
637.5 microseconds per iteration
% time {r_lcs thisisatest testing123testing} 10
1275566.8 microseconds per iteration</
=={{header|Ursala}}==
This uses the same recursive algorithm as in the Haskell example,
and works on lists of any type.
<
lcs = ~&alrB^& ~&E?abh/~&alh2fabt2RC @faltPrXlrtPXXPW leql?/~&r ~&l</
test program:
<
example = lcs('thisisatest','testing123testing')</
{{out}}
<pre>'tsitest'</pre>
Line 3,367:
=={{header|Wren}}==
{{trans|Kotlin}}
<
lcs = Fn.new { |x, y|
if (x.count == 0 || y.count == 0) return ""
Line 3,380:
var x = "thisisatest"
var y = "testing123testing"
System.print(lcs.call(x, y))</
{{out}}
Line 3,390:
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}}
|