Longest common subsequence: Difference between revisions
m
→{{header|EasyLang}}
(Corrected definitions made in the introduction.) |
|||
| (12 intermediate revisions by 6 users not shown) | |||
Line 19:
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.
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''.▼
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.
Line 323:
=={{header|BASIC}}==
==={{header|QuickBASIC}}===
{{works with|QuickBasic|4.5}}
{{trans|Java}}
Line 340 ⟶ 341:
END IF
END FUNCTION</syntaxhighlight>
=={{header|BASIC256}}==
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());
auto prefix = index3 > 0 ? chains[index3 - 1] : nullptr;▼
auto last = make_shared<Pair>(index1, index2, prefix);▼
▲ }
}
else if (index2 <
// Update
*limit =
chains[index3] =
▲ }
}
}▼
}
▲ }
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) {
}
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(
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,151 ⟶ 2,195:
===Alternate letting regex do all the work===
<syntaxhighlight lang="perl">
use warnings;
use feature 'bitwise';
print "lcs is ", lcs('thisisatest', 'testing123testing'), "\n";
Line 2,161 ⟶ 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,169 ⟶ 2,212:
}</syntaxhighlight>
{{out}}
<pre>lcs is
=={{header|Phix}}==
Line 3,167 ⟶ 3,210:
<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,358 ⟶ 3,401:
=={{header|Wren}}==
{{trans|Kotlin}}
<syntaxhighlight lang="
lcs = Fn.new { |x, y|
if (x.count == 0 || y.count == 0) return ""
| |||