Longest common subsequence: Difference between revisions
Content deleted Content added
m →{{header|BASIC}}: It's QuickBASIC, not BASIC in general. |
PascalABC.NET |
||
(10 intermediate revisions by 4 users not shown) | |||
Line 494:
=={{header|C++}}==
'''Hunt and Szymanski algorithm'''
<syntaxhighlight lang="cpp"
#include <stdint.h>
#include <string>
#include <memory> // for shared_ptr<>
Line 507 ⟶ 508:
class LCS {
protected:
//
class Pair {
public:
Line 527 ⟶ 528:
typedef deque<shared_ptr<Pair>> PAIRS;
typedef deque<uint32_t> INDEXES;
typedef unordered_map<char, INDEXES> CHAR_TO_INDEXES_MAP;
typedef deque<INDEXES*> MATCHES;
static uint32_t FindLCS(
MATCHES& indexesOf2MatchedByIndex1, shared_ptr<Pair>* pairs) {
auto traceLCS = pairs != nullptr;
PAIRS chains;
//
//[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 : indexesOf2MatchedByIndex1) {
for
// Each index1, index2 pair corresponds to a match
auto index3
if (limit ==
// Refresh
limit = prev(prefixEnd.end());
if (traceLCS) {
}
else if (index2 <
// Update
*limit =
if (traceLCS) {
chains[index3] =
}
}
} // next index2
index1++;
Line 605 ⟶ 601:
if (traceLCS) {
// Return the LCS as a linked list of matched index pairs:
auto last = chains.
// Reverse longest chain
*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 m*n comparisons by using CHAR_TO_INDEXES_MAP to
Line 622 ⟶ 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;
Line 634 ⟶ 639:
}
static string Select(shared_ptr<Pair> pairs, uint32_t length,
bool right, const string& s1, const string& s2) {
string buffer;
Line 646 ⟶ 651:
public:
static string Correspondence(const string& s1, const string& s2) {
CHAR_TO_INDEXES_MAP indexesOf2MatchedByChar;
MATCHES indexesOf2MatchedByIndex1; // holds references into indexesOf2MatchedByChar
Line 656 ⟶ 661:
};</syntaxhighlight>
'''Example''':
<syntaxhighlight lang="cpp">
auto s =
cout << s << endl;</syntaxhighlight>
More fully featured examples are available at [https://github.com/CNHume/Samples/tree/master/C%2B%2B/LCS Samples/C++/LCS].
=={{header|Clojure}}==
Line 973 ⟶ 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}}==
Line 2,132 ⟶ 2,176:
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>
Line 3,166 ⟶ 3,249:
<syntaxhighlight lang="ruby">func lcs(xstr, ystr) is cached {
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,357 ⟶ 3,440:
=={{header|Wren}}==
{{trans|Kotlin}}
<syntaxhighlight lang="
lcs = Fn.new { |x, y|
if (x.count == 0 || y.count == 0) return ""
|