Longest common subsequence: Difference between revisions
Content deleted Content added
m Minor editorial correction. |
PascalABC.NET |
||
(46 intermediate revisions by 11 users not shown) | |||
Line 1:
{{task}}[[Category:Recursion]][[Category:Memoization]]
'''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'' ≡ ''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.
An ordered pair (i, j) will be referred to as a match if ''A''[i] = ''B''[j], where 0 ≤ i < m and 0 ≤ j < n.
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 < i2 and j2 < j1 (or i2 < i1 and j1 < j2) then neither p1 ≤ p2 nor p1 ≥ p2 are possible, and we say p1 and p2 are ''incomparable''.
Define the ''strict'' product-order (<) over ordered pairs, such that (i1, j1) < (i2, j2) ⇔ i1 < i2 and j1 < j2. We define (>) similarly.
A chain '''C''' is a subset of '''M''' consisting of at least one element m; and where either m1 < m2 or m1 > m2 for every pair of distinct elements m1 and m2. An antichain '''D''' is any subset of '''M''' in which every pair of distinct elements m1 and m2 are incomparable.
A chain can be visualized as a strictly increasing curve that passes through matches (i, j) in the m*n coordinate space of '''M'''[i, j].
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 O(''m*n'') quadratic growth. This occurs, for example, in the Bioinformatics application of nucleotide and protein sequencing.
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.
This quadratic time dependency may become prohibitive, given very long input strings. Thus, heuristics are often favored over optimal Dynamic Programming solutions.
In the application of comparing file revisions, records from the input files form a large symbol space; and the number of symbols approaches the length of the LCS. In this case the number of matches reduces to linear, O(''n'') growth.
A binary search optimization due to [Hunt and Szymanski 1977] can be applied to the basic Dynamic Programming approach, resulting in an expected performance of O(''n log m''). Performance can degrade to O(''m*n log m'') time in the worst case, as the number of matches grows to O(''m*n'').
'''Note'''
[Rick 2000] describes a linear-space algorithm with a time bound of O(''n*s + p*min(m, n - p)'').
'''Legend'''
A, B are input strings of lengths m, n respectively
p is the length of the LCS
M is the set of matches (i, j) such that A[i] = B[j]
r is the magnitude of M
s is the magnitude of the alphabet Σ of distinct symbols in A + B
'''References'''
[Dilworth 1950] "A decomposition theorem for partially ordered sets"
by Robert P. Dilworth, published January 1950,
Annals of Mathematics [Volume 51, Number 1, ''pp.'' 161-166]
[Goeman and Clausen 2002] "A New Practical Linear Space Algorithm for the Longest Common
Subsequence Problem" by Heiko Goeman and Michael Clausen,
published 2002, Kybernetika [Volume 38, Issue 1, ''pp.'' 45-66]
[Hirschberg 1975] "A linear space algorithm for computing maximal common subsequences"
by Daniel S. Hirschberg, published June 1975
Communications of the ACM [Volume 18, Number 6, ''pp.'' 341-343]
[Hunt and McIlroy 1976] "An Algorithm for Differential File Comparison"
by James W. Hunt and M. Douglas McIlroy, June 1976
Computing Science Technical Report, Bell Laboratories 41
[Hunt and Szymanski 1977] "A Fast Algorithm for Computing Longest Common Subsequences"
by James W. Hunt and Thomas G. Szymanski, published May 1977
Communications of the ACM [Volume 20, Number 5, ''pp.'' 350-353]
[Rick 2000] "Simple and fast linear space computation of longest common subsequences"
by Claus Rick, received 17 March 2000, Information Processing Letters,
Elsevier Science [Volume 75, ''pp.'' 275–281]
<br />
'''Examples'''
The sequences "1234" and "1224533324" have an LCS of "1234":
'''<u>1234</u>'''
'''<u>12</u>'''245'''<u>3</u>'''332'''<u>4</u>'''
For a string example, consider the sequences "thisisatest" and "testing123testing". An LCS would be "tsitest":
'''<u>t</u>'''hi'''<u>si</u>'''sa'''<u>test</u>'''
Line 37 ⟶ 97:
{{trans|Python}}
<
V lengths = [[0] * (b.len+1)] * (a.len+1)
L(x) a
Line 56 ⟶ 116:
print(lcs(‘1234’, ‘1224533324’))
print(lcs(‘thisisatest’, ‘testing123testing’))</
{{out}}
Line 66 ⟶ 126:
=={{header|Ada}}==
Using recursion:
<
procedure Test_LCS is
Line 90 ⟶ 150:
begin
Put_Line (LCS ("thisisatest", "testing123testing"));
end Test_LCS;</
{{out}}
<pre>
Line 96 ⟶ 156:
</pre>
Non-recursive solution:
<
procedure Test_LCS is
Line 140 ⟶ 200:
begin
Put_Line (LCS ("thisisatest", "testing123testing"));
end Test_LCS;</
{{out}}
<pre>
Line 151 ⟶ 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 165 ⟶ 225:
END # lcs #;
print((lcs ("thisisatest", "testing123testing"), new line))
)</
{{out}}
<pre>
Line 173 ⟶ 233:
=={{header|APL}}==
{{works with|Dyalog APL}}
<
⎕IO←0
betterof←{⊃(</+/¨⍺ ⍵)⌽⍺ ⍵} ⍝ better of 2 selections
Line 193 ⟶ 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 225 ⟶ 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 244 ⟶ 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 262 ⟶ 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 278 ⟶ 373:
y$ = FNlcs(LEFT$(a$), b$)
IF LEN(y$) > LEN(x$) SWAP x$,y$
= x$</
'''Output:'''
<pre>
Line 284 ⟶ 379:
tsitest
</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.
<syntaxhighlight lang="bqn">LCS ← ¯1 ⊑ "" <⊸∾ ""¨∘⊢ ⊣⍟(>○≠){𝕩𝔽¨𝔽`𝕨∾¨""<⊸»𝕩}˝ (=⌜⥊¨⊣)⟜⌽</syntaxhighlight>
Output:
<syntaxhighlight lang="bqn"> "1234" LCS "1224533324"
"1234"
"thisisatest" LCS "testing123testing"
"tsitest"</syntaxhighlight>
=={{header|Bracmat}}==
<
= A a ta B b tb prefix
. !arg:(?prefix.@(?A:%?a ?ta).@(?B:%?b ?tb))
Line 298 ⟶ 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 339 ⟶ 443:
return t;
}
</syntaxhighlight>
Testing
<
char a[] = "thisisatest";
char b[] = "testing123testing";
Line 350 ⟶ 454:
printf("%.*s\n", t, s); // tsitest
return 0;
}</
=={{header|C sharp|C#}}==
===With recursion===
<
namespace LCS
Line 386 ⟶ 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 443 ⟶ 508:
class LCS {
protected:
//
class Pair {
public:
Line 463 ⟶ 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 554 ⟶ 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 578 ⟶ 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 603 ⟶ 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 637 ⟶ 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 668 ⟶ 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 683 ⟶ 758:
Here is another version with its own memoization macro:
<
(let ((hash-name (gensym)))
`(let ((,hash-name (make-hash-table :test 'equal)))
Line 696 ⟶ 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 708 ⟶ 783:
===Recursive version===
<
T[] lcs(T)(in T[] a, in T[] b) pure nothrow @safe {
Line 720 ⟶ 795:
void main() {
lcs("thisisatest", "testing123testing").writeln;
}</
{{out}}
<pre>tsitest</pre>
Line 726 ⟶ 801:
===Faster dynamic programming version===
The output is the same.
<
T[] lcs(T)(in T[] a, in T[] b) pure /*nothrow*/ {
Line 755 ⟶ 830:
void main() {
lcs("thisisatest", "testing123testing").writeln;
}</
===Hirschberg algorithm version===
Line 764 ⟶ 839:
Adapted from Python code: http://wordaligned.org/articles/longest-common-subsequence
<
uint[] lensLCS(R)(R xs, R ys) pure nothrow @safe {
Line 824 ⟶ 899:
void main() {
lcsString("thisisatest", "testing123testing").writeln;
}</
=={{header|Dart}}==
<
String lcsRecursion(String a, String b) {
Line 894 ⟶ 969:
print("lcsRecursion('x', 'x') = ${lcsRecursion('x', 'x')}");
}
</syntaxhighlight>
{{out}}
<pre>lcsDynamic('1234', '1224533324') = 1234
Line 905 ⟶ 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 917 ⟶ 1,029:
(define $lcs (compose common-seqs rac))
</syntaxhighlight>
'''Output:'''
<
> (lcs "thisisatest" "testing123testing"))
"tsitest"
</syntaxhighlight>
=={{header|Elixir}}==
Line 929 ⟶ 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 942 ⟶ 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 985 ⟶ 1,097:
IO.puts LCS.lcs("thisisatest","testing123testing")
IO.puts LCS.lcs("1234","1224533324")</
{{out}}
Line 996 ⟶ 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,038 ⟶ 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,073 ⟶ 1,185:
Result
end.
</syntaxhighlight>
Similar to the above, but without using the process dictionary:
<
-module(lcs).
Line 1,116 ⟶ 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,146 ⟶ 1,258:
(lcs (split "thisisatest") (split "testing123testing"))))
0
</syntaxhighlight>
=={{header|Factor}}==
<
"thisisatest" "testing123testing" lcs print</
{{out}}
<pre>
Line 1,160 ⟶ 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,197 ⟶ 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,216 ⟶ 1,328:
Print LCS("1234", "1224533324")
Print LCS("thisisatest", "testing123testing")
Sleep</
Line 1,223 ⟶ 1,335:
===Recursion===
Brute force
<
aLen := len(a)
bLen := len(b)
Line 1,237 ⟶ 1,349:
}
return y
}</
===Dynamic Programming===
<
arunes := []rune(a)
brunes := []rune(b)
Line 1,281 ⟶ 1,393:
}
return string(s)
}</
=={{header|Groovy}}==
Recursive solution:
<
if (xstr == "" || ystr == "") {
return "";
Line 1,307 ⟶ 1,419:
println(lcs("1234", "1224533324"));
println(lcs("thisisatest", "testing123testing"));</
{{out}}
<pre>1234
Line 1,316 ⟶ 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,322 ⟶ 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,338 ⟶ 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,353 ⟶ 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,367 ⟶ 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,378 ⟶ 1,490:
lcs xs ys = maximumBy (comparing length) $ intersect (subsequences xs) (subsequences ys)
main = print $ lcs "thisisatest" "testing123testing"</
{{out}}
<pre>"tsitest"</pre>
Line 1,387 ⟶ 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,422 ⟶ 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,430 ⟶ 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,477 ⟶ 1,589:
return (x.length() > y.length()) ? x : y;
}
}</
===Dynamic Programming===
<
int[][] lengths = new int[a.length()+1][b.length()+1];
Line 1,510 ⟶ 1,622:
return sb.reverse().toString();
}</
=={{header|JavaScript}}==
Line 1,516 ⟶ 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,529 ⟶ 1,641:
return (x.length > y.length) ? x : y;
}
}</
ES6 recursive implementation
<
const longest = (xs, ys) => (xs.length > ys.length) ? xs : ys;
Line 1,543 ⟶ 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,582 ⟶ 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,588 ⟶ 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,602 ⟶ 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,647 ⟶ 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,665 ⟶ 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,733 ⟶ 1,845:
@time lcsrecursive("thisisatest", "testing123testing")
@show lcsdynamic("thisisatest", "testing123testing")
@time lcsdynamic("thisisatest", "testing123testing")</
{{out}}
Line 1,742 ⟶ 1,854:
=={{header|Kotlin}}==
<
fun lcs(x: String, y: String): String {
Line 1,758 ⟶ 1,870:
val y = "testing123testing"
println(lcs(x, y))
}</
{{out}}
Line 1,766 ⟶ 1,878:
=={{header|Liberty BASIC}}==
<syntaxhighlight lang="lb">
'variation of BASIC example
w$="aebdef"
Line 1,798 ⟶ 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,810 ⟶ 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,830 ⟶ 1,942:
end
print( LCS( "thisisatest", "testing123testing" ) )</
=={{header|M4}}==
<
define(`get2d',`defn($1[$2][$3])')
define(`tryboth',
Line 1,853 ⟶ 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,884 ⟶ 1,996:
===Recursion===
{{trans|Python}}
<
if x == "" or y == "":
return ""
Line 1,896 ⟶ 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,902 ⟶ 2,014:
===Dynamic Programming===
{{trans|Python}}
<
var ls = newSeq[seq[int]](a.len+1)
for i in 0 .. a.len:
Line 1,929 ⟶ 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,943 ⟶ 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,966 ⟶ 2,078:
result
in
lcs xs ys</
===Dynamic programming===
<
let xs = Array.of_list xs'
and ys = Array.of_list ys' in
Line 1,983 ⟶ 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 1,995 ⟶ 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,008 ⟶ 2,120:
Recursive solution:
<
fun {LCS Xs Ys}
case [Xs Ys]
Line 2,022 ⟶ 2,134:
end
in
{System.showInfo {LCS "thisisatest" "testing123testing"}}</
=={{header|Pascal}}==
{{trans|Fortran}}
<
function lcs(a, b: string): string;
Line 2,059 ⟶ 2,171:
s2 := '1224533324';
writeln (lcs(s1, s2));
end.</
{{out}}
<pre>:> ./LongestCommonSequence
tsitest
1234
</pre>
=={{header|PascalABC.NET}}==
<syntaxhighlight lang="delphi">
function Lengths(x,y: string): array[,] of integer;
begin
var (m,n) := (x.Length,y.Length);
var C := new integer[m+1, n+1]; // filled with zeroes
for var i:=1 to m do
for var j:=1 to n do
if x[i] = y[j] then
C[i,j] := C[i-1,j-1] + 1
else C[i,j] := max(C[i,j-1], C[i-1,j]);
Result := C;
end;
function lcshelper(x,y: string; i,j: integer): string;
begin
var C := Lengths(x,y);
if (i = 0) or (j = 0) then
Result := ''
else if X[i] = Y[j] then
Result := lcshelper(X, Y, i-1, j-1) + X[i]
else if C[i,j-1] > C[i-1,j] then
Result := lcshelper(X, Y, i, j-1)
else Result := lcshelper(X, Y, i-1, j)
end;
function lcs(x,y: string) := lcshelper(x,y,x.Length,y.Length);
begin
Println(lcs('1234','1224533324'));
Println(lcs('thisisatest','testing123testing'));
end.
</syntaxhighlight>
{{out}}
<pre>
1234
tsitest
</pre>
=={{header|Perl}}==
<
my ($a, $b) = @_;
if (!length($a) || !length($b)) {
Line 2,080 ⟶ 2,231:
}
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,093 ⟶ 2,243:
{
my ($c, $d) = @_;
for my $len ( reverse 1 .. length($c &. $d) )
{
"$c\n$d" =~ join '.*', ('(.)') x $len, "\n", map "\\$_", 1 .. $len and
Line 2,099 ⟶ 2,249:
}
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()).
<!--<syntaxhighlight lang="phix">(phixonline)-->
<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: #004080;">sequence</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">""</span>
<span style="color: #008080;">if</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">a</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">and</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">b</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
<span style="color: #008080;">if</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;">then</span>
<span style="color: #000000;">res</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;">1</span><span style="color: #0000FF;">..-</span><span style="color: #000000;">2</span><span style="color: #0000FF;">],</span><span style="color: #000000;">b</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..-</span><span style="color: #000000;">2</span><span style="color: #0000FF;">])&</span><span style="color: #000000;">a</span><span style="color: #0000FF;">[$]</span>
<span
<span style="color: #004080;">sequence</span> <span style="color: #000000;">l</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: #000000;">1</span><span style="color: #0000FF;">..-</span><span style="color: #000000;">2</span><span style="color: #0000FF;">]),</span>
<span style="color: #000000;">r</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;">1</span><span style="color: #0000FF;">..-</span><span style="color: #000000;">2</span><span style="color: #0000FF;">],</span><span style="color: #000000;">b</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">l</span><span style="color: #0000FF;">)></span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">r</span><span style="color: #0000FF;">)?</span><span style="color: #000000;">l</span><span style="color: #0000FF;">:</span><span style="color: #000000;">r</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">res</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">constant</span> <span style="color: #000000;">tests</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{{</span><span style="color: #008000;">"1234"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"1224533324"</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{</span><span style="color: #008000;">"thisisatest"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"testing123testing"</span><span style="color: #0000FF;">}}</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tests</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">string</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: #0000FF;">=</span> <span style="color: #000000;">tests</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</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>
<!--</syntaxhighlight>-->
{{out}}
<pre>
Line 2,132 ⟶ 2,285:
===Alternate version===
same output
<!--<syntaxhighlight lang="phix">(phixonline)-->
<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: #004080;">sequence</span> <span style="color: #000000;">C</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">Y</span><span style="color: #0000FF;">)+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">),</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">X</span><span style="color: #0000FF;">)+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">X</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">Y</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">X</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]=</span><span style="color: #000000;">Y</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">C</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">][</span><span style="color: #000000;">j</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">:=</span> <span style="color: #000000;">C</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">][</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]+</span><span style="color: #000000;">1</span>
<span style="color: #000000;">C</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">][</span><span style="color: #000000;">j</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">:=</span> <span style="color: #7060A8;">max</span><span style="color: #0000FF;">(</span><span style="color: #000000;">C</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">][</span><span style="color: #000000;">j</span><span style="color: #0000FF;">],</span> <span style="color: #000000;">C</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">][</span><span style="color: #000000;">j</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">])</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">C</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">backtrack</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">C</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: #004080;">integer</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">or</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
<span style="color: #008080;">return</span> <span style="color: #008000;">""</span>
<span style="color: #008080;">elsif</span> <span style="color: #000000;">X</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]=</span><span style="color: #000000;">Y</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]</span> <span style="color: #008080;">then</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">backtrack</span><span style="color: #0000FF;">(</span><span style="color: #000000;">C</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">X</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">Y</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span> <span style="color: #0000FF;">&</span> <span style="color: #000000;">X</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">else</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">C</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">][</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]></span><span style="color: #000000;">C</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">][</span><span style="color: #000000;">j</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> <span style="color: #008080;">then</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">backtrack</span><span style="color: #0000FF;">(</span><span style="color: #000000;">C</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">X</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">Y</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">else</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">backtrack</span><span style="color: #0000FF;">(</span><span style="color: #000000;">C</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">X</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">Y</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</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: #004080;">sequence</span> <span style="color: #000000;">b</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">backtrack</span><span style="color: #0000FF;">(</span><span style="color: #000000;">LCSLength</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: #000000;">a</span><span style="color: #0000FF;">,</span><span style="color: #000000;">b</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">a</span><span style="color: #0000FF;">),</span><span style="color: #7060A8;">length</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;">function</span>
<span style="color: #008080;">constant</span> <span style="color: #000000;">tests</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{{</span><span style="color: #008000;">"1234"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"1224533324"</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{</span><span style="color: #008000;">"thisisatest"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"testing123testing"</span><span style="color: #0000FF;">}}</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tests</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">string</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: #0000FF;">=</span> <span style="color: #000000;">tests</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</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>
<!--</syntaxhighlight>-->
=={{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
[XMJYAUZ,MZJAWXU] : MJAU
[1234,1224533324] : 1234
[beginning-middle-ending,beginning-diddle-dum-ending] : beginning-iddle-ending</pre>
=={{header|PicoLisp}}==
<
(when A
(conc
Line 2,183 ⟶ 2,417:
(commonSequences
(chop "thisisatest")
(chop "testing123testing") ) )</
{{out}}
<pre>-> ("t" "s" "i" "t" "e" "s" "t")</pre>
Line 2,189 ⟶ 2,423:
=={{header|PowerShell}}==
Returns a sequence (array) of a type:
<syntaxhighlight lang="powershell">
function Get-Lcs ($ReferenceObject, $DifferenceObject)
{
Line 2,237 ⟶ 2,471:
$longestCommonSubsequence
}
</syntaxhighlight>
Returns the character array as a string:
<syntaxhighlight lang="powershell">
(Get-Lcs -ReferenceObject "thisisatest" -DifferenceObject "testing123testing") -join ""
</syntaxhighlight>
{{Out}}
<pre>
Line 2,247 ⟶ 2,481:
</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,258 ⟶ 2,492:
</pre>
Given two lists of objects, return the LCS of the ID property:
<syntaxhighlight lang="powershell">
$list1
Line 2,284 ⟶ 2,518:
Get-Lcs -ReferenceObject $list1.ID -DifferenceObject $list2.ID
</syntaxhighlight>
{{Out}}
<pre>
Line 2,297 ⟶ 2,531:
===Recursive Version===
First version:
<
time(lcs("thisisatest", "testing123testing", Lcs)),
writef('%s',[Lcs]).
Line 2,316 ⟶ 2,550:
length(L1,Length1),
length(L2,Length2),
((Length1 > Length2) -> Longest = L1; Longest = L2).</
Second version, with memoization:
<
:- dynamic lcs_db/3.
Line 2,346 ⟶ 2,580:
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,379 ⟶ 2,613:
OpenConsole()
PrintN( lcs("thisisatest", "testing123testing"))
PrintN("Press any key to exit"): Repeat: Until Inkey() <> ""</
=={{header|Python}}==
Line 2,386 ⟶ 2,620:
===Recursion===
This solution is similar to the Haskell one. It is slow.
<
"""
>>> lcs('thisisatest', 'testing123testing')
Line 2,397 ⟶ 2,631:
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,420 ⟶ 2,654:
result += a[i-1]
return result</
=={{header|Racket}}==
<
(define (longest xs ys)
(if (> (length xs) (length ys))
Line 2,448 ⟶ 2,682:
(list->string (lcs/list (string->list sx) (string->list sy))))
(lcs "thisisatest" "testing123testing")</
{{out}}
<pre>"tsitest"></pre>
Line 2,457 ⟶ 2,691:
{{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,466 ⟶ 2,700:
}
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,501 ⟶ 2,735:
}
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,559 ⟶ 2,785:
}
};
</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,587 ⟶ 2,813:
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,602 ⟶ 2,828:
=={{header|Ring}}==
<
see longest("1267834", "1224533324") + nl
Line 2,619 ⟶ 2,845:
lcs = x2
return lcs ok ok
</syntaxhighlight>
Output:
<pre>
Line 2,629 ⟶ 2,855:
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,642 ⟶ 2,868:
[lcs(xstr, ys), lcs(xs, ystr)].max_by {|x| x.size}
end
end</
===Dynamic programming===
Line 2,649 ⟶ 2,875:
Walker class for the LCS matrix:
<
SELF, LEFT, UP, DIAG = [0,0], [0,-1], [-1,0], [-1,-1]
Line 2,715 ⟶ 2,941:
puts lcs('thisisatest', 'testing123testing')
puts lcs("rosettacode", "raisethysword")
end</
{{out}}
Line 2,725 ⟶ 2,951:
=={{header|Run BASIC}}==
<
b$ = "cacbac"
print lcs$(a$,b$)
Line 2,751 ⟶ 2,977:
END IF
[ext]
END FUNCTION</
=={{header|Rust}}==
Dynamic programming version:
<
use std::cmp;
Line 2,811 ⟶ 3,037:
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,827 ⟶ 3,053:
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,836 ⟶ 3,062:
val (s1, s2) = (lcsRec(a +: as, bs), lcsRec(as, b +: bs))
if(s1.length > s2.length) s1 else s2
}</
{{out}}
Line 2,846 ⟶ 3,072:
{{works with|Scala 2.9.3}}
Recursive version:
<
case (_, Nil) => Nil
case (Nil, _) => Nil
Line 2,856 ⟶ 3,082:
}
}
}</
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,875 ⟶ 3,101:
}
}
}</
{{out}}
Line 2,885 ⟶ 3,111:
Port from Clojure.
<
;; using srfi-69
(define (memoize proc)
Line 2,915 ⟶ 3,141:
'()))
'()))))
</syntaxhighlight>
Testing:
<
(test-group
Line 2,932 ⟶ 3,158:
(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,963 ⟶ 3,189:
writeln(lcs("thisisatest", "testing123testing"));
writeln(lcs("1234", "1224533324"));
end func;</
Output:
Line 2,976 ⟶ 3,202:
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 2,997 ⟶ 3,223:
lcsBack(args[1], args[2]) when size(args) >=2
else
lcsBack("thisisatest", "testing123testing");</
{{out}}
Line 3,006 ⟶ 3,232:
=={{header|SETL}}==
Recursive; Also works on tuples (vectors)
<
return if #a > #b then a else b end;
end .longest;
Line 3,018 ⟶ 3,244:
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,046 ⟶ 3,272:
===Recursion===
{{trans|Java}}
<
[
s1 isEmpty \/ s2 isEmpty ifTrue: [^ {}].
Line 3,055 ⟶ 3,281:
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,081 ⟶ 3,307:
index2: index2 - 1]]
] writingAs: s1) reverse
].</
=={{header|Swift}}==
Swift 5.1
===Recursion===
<
if s1.count == 0 || s2.count == 0 {
return ""
Line 3,098 ⟶ 3,324:
return str1.count > str2.count ? str1 : str2
}
}</
===Dynamic Programming===
<
var lens = Array(
repeating:Array(repeating: 0, count: s2.count + 1),
Line 3,133 ⟶ 3,359:
return String(returnStr.reversed())
}</
=={{header|Tcl}}==
===Recursive===
{{trans|Java}}
<
if {$a eq "" || $b eq ""} {return ""}
set a_ [string range $a 1 end]
Line 3,149 ⟶ 3,375:
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,191 ⟶ 3,417:
}
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,214 ⟶ 3,440:
=={{header|Wren}}==
{{trans|Kotlin}}
<
lcs = Fn.new { |x, y|
if (x.count == 0 || y.count == 0) return ""
Line 3,227 ⟶ 3,453:
var x = "thisisatest"
var y = "testing123testing"
System.print(lcs.call(x, y))</
{{out}}
Line 3,237 ⟶ 3,463:
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}}
|