Longest common subsequence: Difference between revisions
m
→{{header|EasyLang}}
m (Improved discussion of M interpreted as an m*n boolean matrix. Simplified O(n) terms.) |
|||
(27 intermediate revisions by 9 users not shown) | |||
Line 2:
'''Introduction'''
Define a ''subsequence'' to be any output string obtained by deleting zero or more symbols from an input string.
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.
Let ''A''
An ordered pair (i, j) will be
The set of matches '''M''' defines a relation over matches: '''M'''[i, j] ⇔ (i, j) ∈ '''M'''.
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.
We say ordered pairs p1 and p2 are ''comparable'' if either p1 ≤ p2 or p1 ≥ p2 holds. If i1 &
Define the ''strict'' product-order (<) over ordered pairs, such that (i1, j1) < (i2, j2) ⇔ i1 < i2 and j1 < j2. We define (>) similarly.
Every Common Sequence of length ''q'' corresponds to a chain of cardinality ''q'', over the set of matches '''M'''. Thus, finding an LCS can be restated as the problem of finding a chain of maximum cardinality ''p''.
According to [Dilworth 1950], this cardinality ''p'' equals the minimum number of disjoint antichains into which '''M''' can be decomposed. Note that such a decomposition into the minimal number p of disjoint antichains may not be unique.
'''Background'''
Where the number of symbols appearing in matches is small relative to the length of the input strings, reuse of the symbols increases; and the number of matches will tend towards
The
This quadratic time dependency may become prohibitive, given very long input strings. Thus, heuristics are often favored over optimal Dynamic Programming solutions.
Line 46:
A, B are input strings of lengths m, n respectively
p is the length of the LCS
M is the set of
r is the magnitude of M
s is the magnitude of the alphabet Σ of distinct symbols in
'''References'''
Line 97:
{{trans|Python}}
<
V lengths = [[0] * (b.len+1)] * (a.len+1)
L(x) a
Line 116:
print(lcs(‘1234’, ‘1224533324’))
print(lcs(‘thisisatest’, ‘testing123testing’))</
{{out}}
Line 126:
=={{header|Ada}}==
Using recursion:
<
procedure Test_LCS is
Line 150:
begin
Put_Line (LCS ("thisisatest", "testing123testing"));
end Test_LCS;</
{{out}}
<pre>
Line 156:
</pre>
Non-recursive solution:
<
procedure Test_LCS is
Line 200:
begin
Put_Line (LCS ("thisisatest", "testing123testing"));
end Test_LCS;</
{{out}}
<pre>
Line 211:
{{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 225:
END # lcs #;
print((lcs ("thisisatest", "testing123testing"), new line))
)</
{{out}}
<pre>
Line 233:
=={{header|APL}}==
{{works with|Dyalog APL}}
<
⎕IO←0
betterof←{⊃(</+/¨⍺ ⍵)⌽⍺ ⍵} ⍝ better of 2 selections
Line 253:
this ∇ 1↓[1]⍵ ⍝ keep looking
}sstt
}</
=={{header|Arturo}}==
{{trans|Python}}
<syntaxhighlight lang="rebol">lcs: function [a,b][
ls: new array.of: @[inc size a, inc size b] 0
loop.with:'i a 'x [
loop.with:'j b 'y [
ls\[i+1]\[j+1]: (x=y)? -> ls\[i]\[j] + 1
-> max @[ls\[i+1]\[j], ls\[i]\[j+1]]
]
]
[result, x, y]: @[new "", size a, size b]
while [and? [x > 0][y > 0]][
if? ls\[x]\[y] = ls\[x-1]\[y] -> x: x-1
else [
if? ls\[x]\[y] = ls\[x]\[y-1] -> y: y-1
else [
result: a\[x-1] ++ result
x: x-1
y: y-1
]
]
]
return result
]
print lcs "1234" "1224533324"
print lcs "thisisatest" "testing123testing"</syntaxhighlight>
{{out}}
<pre>1234
tsitest</pre>
=={{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
Line 285 ⟶ 320:
}
Return t
}</
=={{header|BASIC}}==
==={{header|QuickBASIC}}===
{{works with|QuickBasic|4.5}}
{{trans|Java}}
<
IF LEN(a$) = 0 OR LEN(b$) = 0 THEN
lcs$ = ""
Line 304 ⟶ 340:
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 322 ⟶ 357:
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 338 ⟶ 373:
y$ = FNlcs(LEFT$(a$), b$)
IF LEN(y$) > LEN(x$) SWAP x$,y$
= x$</
'''Output:'''
<pre>
Line 347 ⟶ 382:
=={{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 367 ⟶ 402:
& :?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 408 ⟶ 443:
return t;
}
</syntaxhighlight>
Testing
<
char a[] = "thisisatest";
char b[] = "testing123testing";
Line 419 ⟶ 454:
printf("%.*s\n", t, s); // tsitest
return 0;
}</
=={{header|C sharp|C#}}==
===With recursion===
<
namespace LCS
Line 455 ⟶ 490:
}
}
}</
=={{header|C++}}==
'''Hunt and Szymanski algorithm'''
<syntaxhighlight lang="cpp">
#include <stdint.h>
#include <string>
#include <memory> // for shared_ptr<>
#include <iostream>
#include <deque>
#include <
#include <algorithm> // for lower_bound()
#include <iterator> // for next() and prev()
Line 472 ⟶ 508:
class LCS {
protected:
//
class Pair {
public:
Line 492 ⟶ 528:
typedef deque<shared_ptr<Pair>> PAIRS;
typedef deque<uint32_t> INDEXES;
typedef
typedef deque<INDEXES*> MATCHES;
static uint32_t FindLCS(
auto
PAIRS
//
//[Assert]After each index1 iteration
// such that the LCS of s1[0:index1] and s2[0:index2] has length index3 + 1
//
uint32_t index1 = 0;
for (const auto& it1 :
for
// Each index1, index2 pair corresponds to a match
//
// Depending on match redundancy, this optimization may reduce the number
// of Pair allocations by factors ranging from 2 up to 10 or more.
if (preferNextIndex2) continue;
if (limit ==
// Insert
prefixEnd.push_back(index2);
// Refresh limit iterator:
limit = prev(prefixEnd.end());
if (traceLCS) {
chains.push_back(pushPair(chains, index3, index1, index2));
}
else if (index2 <
// Update
// Update
*limit = index2;
if (traceLCS) {
}
}
} // next index2
index1++;
} // next index1
if (
// Return the LCS as a linked list of matched index pairs:
auto last =
// Reverse longest
*pairs = Pair::Reverse(last);
}
auto length =
return length;
}
private:
static shared_ptr<Pair> pushPair(
PAIRS& chains, const ptrdiff_t& index3, uint32_t& index1, uint32_t& index2) {
auto prefix = index3 > 0 ? chains[index3 - 1] : nullptr;
return make_shared<Pair>(index1, index2, prefix);
}
protected:
//
// Match() avoids
//
//
// The lookup time can be assumed constant in the case of characters.
Line 583 ⟶ 626:
// time will be O(log(m+n)), at most.
//
static void Match(
CHAR_TO_INDEXES_MAP& indexesOf2MatchedByChar, MATCHES& indexesOf2MatchedByIndex1,
const string& s1, const string& s2) {
uint32_t index = 0;
for (const auto& it : s2)
for (const auto& it : s1) {
auto& dq2 =
}
}
static string Select(shared_ptr<Pair> pairs, uint32_t length,
bool right, const string& s1, const string& s2) {
string buffer;
Line 607 ⟶ 651:
public:
static string Correspondence(const string& s1, const string& s2) {
CHAR_TO_INDEXES_MAP indexesOf2MatchedByChar;
MATCHES
Match(
shared_ptr<Pair> pairs; // obtain the LCS as index pairs
auto length =
return Select(pairs, length, false, s1, s2);
}
};</
'''Example''':
<syntaxhighlight lang
auto s =
cout << s << endl;</
More fully featured examples are available at [https://github.com/CNHume/Samples/tree/master/C%2B%2B/LCS Samples/C++/LCS].
=={{header|Clojure}}==
Based on algorithm from Wikipedia.
<
(def lcs
Line 632 ⟶ 678:
(= 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 666 ⟶ 712:
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 697 ⟶ 743:
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 712 ⟶ 758:
Here is another version with its own memoization macro:
<
(let ((hash-name (gensym)))
`(let ((,hash-name (make-hash-table :test 'equal)))
Line 725 ⟶ 771:
((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 737 ⟶ 783:
===Recursive version===
<
T[] lcs(T)(in T[] a, in T[] b) pure nothrow @safe {
Line 749 ⟶ 795:
void main() {
lcs("thisisatest", "testing123testing").writeln;
}</
{{out}}
<pre>tsitest</pre>
Line 755 ⟶ 801:
===Faster dynamic programming version===
The output is the same.
<
T[] lcs(T)(in T[] a, in T[] b) pure /*nothrow*/ {
Line 784 ⟶ 830:
void main() {
lcs("thisisatest", "testing123testing").writeln;
}</
===Hirschberg algorithm version===
Line 793 ⟶ 839:
Adapted from Python code: http://wordaligned.org/articles/longest-common-subsequence
<
uint[] lensLCS(R)(R xs, R ys) pure nothrow @safe {
Line 853 ⟶ 899:
void main() {
lcsString("thisisatest", "testing123testing").writeln;
}</
=={{header|Dart}}==
<
String lcsRecursion(String a, String b) {
Line 923 ⟶ 969:
print("lcsRecursion('x', 'x') = ${lcsRecursion('x', 'x')}");
}
</syntaxhighlight>
{{out}}
<pre>lcsDynamic('1234', '1224533324') = 1234
Line 934 ⟶ 980:
lcsRecursion('', 'x') =
lcsRecursion('x', 'x') = x</pre>
=={{header|EasyLang}}==
{{trans|BASIC256}}
<syntaxhighlight>
func$ right a$ n .
return substr a$ (len a$ - n + 1) n
.
func$ left a$ n .
if n < 0
n = len a$ + n
.
return substr a$ 1 n
.
func$ lcs a$ b$ .
if len a$ = 0 or len b$ = 0
return ""
.
if right a$ 1 = right b$ 1
return lcs left a$ -1 left b$ -1 & right a$ 1
.
x$ = lcs a$ left b$ -1
y$ = lcs left a$ -1 b$
if len x$ > len y$
return x$
else
return y$
.
.
print lcs "1234" "1224533324"
print lcs "thisisatest" "testing123testing"
</syntaxhighlight>
{{out}}
<pre>
1234
tsitest
</pre>
=={{header|Egison}}==
<
(define $common-seqs
(lambda [$xs $ys]
Line 946 ⟶ 1,029:
(define $lcs (compose common-seqs rac))
</syntaxhighlight>
'''Output:'''
<
> (lcs "thisisatest" "testing123testing"))
"tsitest"
</syntaxhighlight>
=={{header|Elixir}}==
Line 958 ⟶ 1,041:
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 971 ⟶ 1,054:
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,014 ⟶ 1,097:
IO.puts LCS.lcs("thisisatest","testing123testing")
IO.puts LCS.lcs("1234","1224533324")</
{{out}}
Line 1,025 ⟶ 1,108:
=={{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,067 ⟶ 1,150:
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,102 ⟶ 1,185:
Result
end.
</syntaxhighlight>
Similar to the above, but without using the process dictionary:
<
-module(lcs).
Line 1,145 ⟶ 1,228:
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,175 ⟶ 1,258:
(lcs (split "thisisatest") (split "testing123testing"))))
0
</syntaxhighlight>
=={{header|Factor}}==
<
"thisisatest" "testing123testing" lcs print</
{{out}}
<pre>
Line 1,189 ⟶ 1,272:
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,226 ⟶ 1,309:
end function lcs
end program lcstest</
=={{header|FreeBASIC}}==
<
Dim As String x, y
If Len(a) = 0 Or Len(b) = 0 Then
Line 1,245 ⟶ 1,328:
Print LCS("1234", "1224533324")
Print LCS("thisisatest", "testing123testing")
Sleep</
Line 1,252 ⟶ 1,335:
===Recursion===
Brute force
<
aLen := len(a)
bLen := len(b)
Line 1,266 ⟶ 1,349:
}
return y
}</
===Dynamic Programming===
<
arunes := []rune(a)
brunes := []rune(b)
Line 1,310 ⟶ 1,393:
}
return string(s)
}</
=={{header|Groovy}}==
Recursive solution:
<
if (xstr == "" || ystr == "") {
return "";
Line 1,336 ⟶ 1,419:
println(lcs("1234", "1224533324"));
println(lcs("thisisatest", "testing123testing"));</
{{out}}
<pre>1234
Line 1,345 ⟶ 1,428:
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,351 ⟶ 1,434:
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,367 ⟶ 1,450:
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,382 ⟶ 1,465:
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,396 ⟶ 1,479:
f [a,b] [c,d]
| null a = longest b c: [b]
| otherwise = (a++d):[b]</
Simple and slow solution:
<
import Data.List
Line 1,407 ⟶ 1,490:
lcs xs ys = maximumBy (comparing length) $ intersect (subsequences xs) (subsequences ys)
main = print $ lcs "thisisatest" "testing123testing"</
{{out}}
<pre>"tsitest"</pre>
Line 1,416 ⟶ 1,499:
{{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,451 ⟶ 1,534:
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,459 ⟶ 1,542:
=={{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,506 ⟶ 1,589:
return (x.length() > y.length()) ? x : y;
}
}</
===Dynamic Programming===
<
int[][] lengths = new int[a.length()+1][b.length()+1];
Line 1,539 ⟶ 1,622:
return sb.reverse().toString();
}</
=={{header|JavaScript}}==
Line 1,545 ⟶ 1,628:
{{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,558 ⟶ 1,641:
return (x.length > y.length) ? x : y;
}
}</
ES6 recursive implementation
<
const longest = (xs, ys) => (xs.length > ys.length) ? xs : ys;
Line 1,572 ⟶ 1,655:
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,611 ⟶ 1,694:
}
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,617 ⟶ 1,700:
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,631 ⟶ 1,714:
}
}
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,676 ⟶ 1,759:
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,694 ⟶ 1,777:
| 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,762 ⟶ 1,845:
@time lcsrecursive("thisisatest", "testing123testing")
@show lcsdynamic("thisisatest", "testing123testing")
@time lcsdynamic("thisisatest", "testing123testing")</
{{out}}
Line 1,771 ⟶ 1,854:
=={{header|Kotlin}}==
<
fun lcs(x: String, y: String): String {
Line 1,787 ⟶ 1,870:
val y = "testing123testing"
println(lcs(x, y))
}</
{{out}}
Line 1,795 ⟶ 1,878:
=={{header|Liberty BASIC}}==
<syntaxhighlight lang="lb">
'variation of BASIC example
w$="aebdef"
Line 1,827 ⟶ 1,910:
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,839 ⟶ 1,922:
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,859 ⟶ 1,942:
end
print( LCS( "thisisatest", "testing123testing" ) )</
=={{header|M4}}==
<
define(`get2d',`defn($1[$2][$3])')
define(`tryboth',
Line 1,882 ⟶ 1,965:
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,913 ⟶ 1,996:
===Recursion===
{{trans|Python}}
<
if x == "" or y == "":
return ""
Line 1,925 ⟶ 2,008:
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,931 ⟶ 2,014:
===Dynamic Programming===
{{trans|Python}}
<
var ls = newSeq[seq[int]](a.len+1)
for i in 0 .. a.len:
Line 1,958 ⟶ 2,041:
echo lcs("1234", "1224533324")
echo lcs("thisisatest", "testing123testing")</
=={{header|OCaml}}==
===Recursion===
from Haskell
<
let rec lcs a b = match a, b with
Line 1,972 ⟶ 2,055:
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 1,995 ⟶ 2,078:
result
in
lcs xs ys</
===Dynamic programming===
<
let xs = Array.of_list xs'
and ys = Array.of_list ys' in
Line 2,012 ⟶ 2,095:
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,024 ⟶ 2,107:
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,037 ⟶ 2,120:
Recursive solution:
<
fun {LCS Xs Ys}
case [Xs Ys]
Line 2,051 ⟶ 2,134:
end
in
{System.showInfo {LCS "thisisatest" "testing123testing"}}</
=={{header|Pascal}}==
{{trans|Fortran}}
<
function lcs(a, b: string): string;
Line 2,088 ⟶ 2,171:
s2 := '1224533324';
writeln (lcs(s1, s2));
end.</
{{out}}
<pre>:> ./LongestCommonSequence
Line 2,096 ⟶ 2,179:
=={{header|Perl}}==
<
my ($a, $b) = @_;
if (!length($a) || !length($b)) {
Line 2,109 ⟶ 2,192:
}
print lcs("thisisatest", "testing123testing") . "\n";</
===Alternate letting regex do all the work===
<syntaxhighlight lang="perl">use strict;
use warnings;
use feature 'bitwise';
print "lcs is ", lcs('thisisatest', 'testing123testing'), "\n";
Line 2,122 ⟶ 2,204:
{
my ($c, $d) = @_;
for my $len ( reverse 1 .. length($c &. $d) )
{
"$c\n$d" =~ join '.*', ('(.)') x $len, "\n", map "\\$_", 1 .. $len and
Line 2,128 ⟶ 2,210:
}
return '';
}</
{{out}}
<pre>lcs is
=={{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,156 ⟶ 2,238:
<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,164 ⟶ 2,246:
===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,204 ⟶ 2,286:
<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.
<syntaxhighlight lang="picat">lcs_wiki(X,Y) = V =>
[C, _Len] = lcs_length(X,Y),
V = backTrace(C,X,Y,X.length+1,Y.length+1).
lcs_length(X, Y) = V=>
M = X.length,
N = Y.length,
C = [[0 : J in 1..N+1] : I in 1..N+1],
foreach(I in 2..M+1,J in 2..N+1)
if X[I-1] == Y[J-1] then
C[I,J] := C[I-1,J-1] + 1
else
C[I,J] := max([C[I,J-1], C[I-1,J]])
end
end,
V = [C, C[M+1,N+1]].
backTrace(C, X, Y, I, J) = V =>
if I == 1; J == 1 then
V = ""
elseif X[I-1] == Y[J-1] then
V = backTrace(C, X, Y, I-1, J-1) ++ [X[I-1]]
else
if C[I,J-1] > C[I-1,J] then
V = backTrace(C, X, Y, I, J-1)
else
V = backTrace(C, X, Y, I-1, J)
end
end.</syntaxhighlight>
===Rule-based===
{{trans|SETL}}
<syntaxhighlight lang="picat">table
lcs_rule(A, B) = "", (A == ""; B == "") => true.
lcs_rule(A, B) = [A[1]] ++ lcs_rule(butfirst(A), butfirst(B)), A[1] == B[1] => true.
lcs_rule(A, B) = longest(lcs_rule(butfirst(A), B), lcs_rule(A, butfirst(B))) => true.
% Return the longest string of A and B
longest(A, B) = cond(A.length > B.length, A, B).
% butfirst (everything except first element)
butfirst(A) = [A[I] : I in 2..A.length].</syntaxhighlight>
===Test===
<syntaxhighlight lang="picat">go =>
Tests = [["thisisatest","testing123testing"],
["XMJYAUZ", "MZJAWXU"],
["1234", "1224533324"],
["beginning-middle-ending","beginning-diddle-dum-ending"]
],
Funs = [lcs_wiki,lcs_rule],
foreach(Fun in Funs)
println(fun=Fun),
foreach(Test in Tests)
printf("%w : %w\n", Test, apply(Fun,Test[1],Test[2]))
end,
nl
end,
nl.</syntaxhighlight>
{{out}}
<pre>fun = lcs_wiki
[thisisatest,testing123testing] : tsitest
[XMJYAUZ,MZJAWXU] : MJAU
[1234,1224533324] : 1234
[beginning-middle-ending,beginning-diddle-dum-ending] : beginning-iddle-ending
fun = lcs_rule
[thisisatest,testing123testing] : tsitest
[XMJYAUZ,MZJAWXU] : MJAU
[1234,1224533324] : 1234
[beginning-middle-ending,beginning-diddle-dum-ending] : beginning-iddle-ending</pre>
=={{header|PicoLisp}}==
<
(when A
(conc
Line 2,218 ⟶ 2,378:
(commonSequences
(chop "thisisatest")
(chop "testing123testing") ) )</
{{out}}
<pre>-> ("t" "s" "i" "t" "e" "s" "t")</pre>
Line 2,224 ⟶ 2,384:
=={{header|PowerShell}}==
Returns a sequence (array) of a type:
<syntaxhighlight lang="powershell">
function Get-Lcs ($ReferenceObject, $DifferenceObject)
{
Line 2,272 ⟶ 2,432:
$longestCommonSubsequence
}
</syntaxhighlight>
Returns the character array as a string:
<syntaxhighlight lang="powershell">
(Get-Lcs -ReferenceObject "thisisatest" -DifferenceObject "testing123testing") -join ""
</syntaxhighlight>
{{Out}}
<pre>
Line 2,282 ⟶ 2,442:
</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,293 ⟶ 2,453:
</pre>
Given two lists of objects, return the LCS of the ID property:
<syntaxhighlight lang="powershell">
$list1
Line 2,319 ⟶ 2,479:
Get-Lcs -ReferenceObject $list1.ID -DifferenceObject $list2.ID
</syntaxhighlight>
{{Out}}
<pre>
Line 2,332 ⟶ 2,492:
===Recursive Version===
First version:
<
time(lcs("thisisatest", "testing123testing", Lcs)),
writef('%s',[Lcs]).
Line 2,351 ⟶ 2,511:
length(L1,Length1),
length(L2,Length2),
((Length1 > Length2) -> Longest = L1; Longest = L2).</
Second version, with memoization:
<
:- dynamic lcs_db/3.
Line 2,381 ⟶ 2,541:
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,414 ⟶ 2,574:
OpenConsole()
PrintN( lcs("thisisatest", "testing123testing"))
PrintN("Press any key to exit"): Repeat: Until Inkey() <> ""</
=={{header|Python}}==
Line 2,421 ⟶ 2,581:
===Recursion===
This solution is similar to the Haskell one. It is slow.
<
"""
>>> lcs('thisisatest', 'testing123testing')
Line 2,432 ⟶ 2,592:
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,455 ⟶ 2,615:
result += a[i-1]
return result</
=={{header|Racket}}==
<
(define (longest xs ys)
(if (> (length xs) (length ys))
Line 2,483 ⟶ 2,643:
(list->string (lcs/list (string->list sx) (string->list sy))))
(lcs "thisisatest" "testing123testing")</
{{out}}
<pre>"tsitest"></pre>
Line 2,492 ⟶ 2,652:
{{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,501 ⟶ 2,661:
}
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,536 ⟶ 2,696:
}
say lcs("thisisatest", "testing123testing");</
===Bit Vector===
Bit parallel dynamic programming with nearly linear complexity O(n). It is fast.
<syntaxhighlight lang="raku"
my (
my (%positions, @Vs, $lcs);
my $S = +^ 0;
my
}
my ($i, $j) =
while ($i ≥ 0 and $j ≥ 0) {
}
$i--
}
}
say lcs("thisisatest", "testing123testing");</
=={{header|ReasonML}}==
<
let longest = (xs, ys) =>
if (List.length(xs) > List.length(ys)) {
Line 2,594 ⟶ 2,746:
}
};
</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,622 ⟶ 2,774:
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,637 ⟶ 2,789:
=={{header|Ring}}==
<
see longest("1267834", "1224533324") + nl
Line 2,654 ⟶ 2,806:
lcs = x2
return lcs ok ok
</syntaxhighlight>
Output:
<pre>
Line 2,664 ⟶ 2,816:
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,677 ⟶ 2,829:
[lcs(xstr, ys), lcs(xs, ystr)].max_by {|x| x.size}
end
end</
===Dynamic programming===
Line 2,684 ⟶ 2,836:
Walker class for the LCS matrix:
<
SELF, LEFT, UP, DIAG = [0,0], [0,-1], [-1,0], [-1,-1]
Line 2,750 ⟶ 2,902:
puts lcs('thisisatest', 'testing123testing')
puts lcs("rosettacode", "raisethysword")
end</
{{out}}
Line 2,760 ⟶ 2,912:
=={{header|Run BASIC}}==
<
b$ = "cacbac"
print lcs$(a$,b$)
Line 2,786 ⟶ 2,938:
END IF
[ext]
END FUNCTION</
=={{header|Rust}}==
Dynamic programming version:
<
use std::cmp;
Line 2,846 ⟶ 2,998:
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,862 ⟶ 3,014:
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,871 ⟶ 3,023:
val (s1, s2) = (lcsRec(a +: as, bs), lcsRec(as, b +: bs))
if(s1.length > s2.length) s1 else s2
}</
{{out}}
Line 2,881 ⟶ 3,033:
{{works with|Scala 2.9.3}}
Recursive version:
<
case (_, Nil) => Nil
case (Nil, _) => Nil
Line 2,891 ⟶ 3,043:
}
}
}</
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 2,910 ⟶ 3,062:
}
}
}</
{{out}}
Line 2,920 ⟶ 3,072:
Port from Clojure.
<
;; using srfi-69
(define (memoize proc)
Line 2,950 ⟶ 3,102:
'()))
'()))))
</syntaxhighlight>
Testing:
<
(test-group
Line 2,967 ⟶ 3,119:
(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 2,998 ⟶ 3,150:
writeln(lcs("thisisatest", "testing123testing"));
writeln(lcs("1234", "1224533324"));
end func;</
Output:
Line 3,011 ⟶ 3,163:
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,032 ⟶ 3,184:
lcsBack(args[1], args[2]) when size(args) >=2
else
lcsBack("thisisatest", "testing123testing");</
{{out}}
Line 3,041 ⟶ 3,193:
=={{header|SETL}}==
Recursive; Also works on tuples (vectors)
<
return if #a > #b then a else b end;
end .longest;
Line 3,053 ⟶ 3,205:
return lcs(a(2..), b) .longest lcs(a, b(2..));
end;
end lcs;</
=={{header|Sidef}}==
<
xstr.is_empty && return xstr
ystr.is_empty && return ystr
var(x, xs, y, ys) = (xstr.
ystr.
if (x == y) {
x + lcs(xs, ys)
} else {
[lcs(xstr, ys), lcs(xs, ystr)].max_by { .len }
}
}
say lcs("thisisatest", "testing123testing")
{{out}}
<pre>
Line 3,081 ⟶ 3,233:
===Recursion===
{{trans|Java}}
<
[
s1 isEmpty \/ s2 isEmpty ifTrue: [^ {}].
Line 3,090 ⟶ 3,242:
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,116 ⟶ 3,268:
index2: index2 - 1]]
] writingAs: s1) reverse
].</
=={{header|Swift}}==
Swift 5.1
===Recursion===
<
if s1.count == 0 || s2.count == 0 {
return ""
Line 3,133 ⟶ 3,285:
return str1.count > str2.count ? str1 : str2
}
}</
===Dynamic Programming===
<
var lens = Array(
repeating:Array(repeating: 0, count: s2.count + 1),
Line 3,168 ⟶ 3,320:
return String(returnStr.reversed())
}</
=={{header|Tcl}}==
===Recursive===
{{trans|Java}}
<
if {$a eq "" || $b eq ""} {return ""}
set a_ [string range $a 1 end]
Line 3,184 ⟶ 3,336:
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,226 ⟶ 3,378:
}
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,249 ⟶ 3,401:
=={{header|Wren}}==
{{trans|Kotlin}}
<
lcs = Fn.new { |x, y|
if (x.count == 0 || y.count == 0) return ""
Line 3,262 ⟶ 3,414:
var x = "thisisatest"
var y = "testing123testing"
System.print(lcs.call(x, y))</
{{out}}
Line 3,272 ⟶ 3,424:
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}}
|