Longest common subsequence: Difference between revisions
m
→{{header|EasyLang}}
(Introduced LCS::pushPair() method. Added static method declarations.) |
|||
(6 intermediate revisions by 4 users not shown) | |||
Line 532:
typedef deque<INDEXES*> MATCHES;
static uint32_t FindLCS(
MATCHES& indexesOf2MatchedByIndex1, shared_ptr<Pair>* pairs) {
auto traceLCS = pairs != nullptr;
PAIRS chains;
Line 543 ⟶ 544:
uint32_t index1 = 0;
for (const auto& it1 : indexesOf2MatchedByIndex1) {
for
// Each index1, index2 pair corresponds to a match
}▼
}
else if (index2 <
// Update
*limit =
if (traceLCS) {
}▼
}
}
}▼
index1++;
Line 602 ⟶ 601:
if (traceLCS) {
// Return the LCS as a linked list of matched index pairs:
auto last = chains.
// Reverse longest chain
*pairs = Pair::Reverse(last);
Line 627 ⟶ 626:
// time will be O(log(m+n)), at most.
//
static void Match(
const string& s1, const string& s2) {
uint32_t index = 0;
Line 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 .
.
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 3,173 ⟶ 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,364 ⟶ 3,401:
=={{header|Wren}}==
{{trans|Kotlin}}
<syntaxhighlight lang="
lcs = Fn.new { |x, y|
if (x.count == 0 || y.count == 0) return ""
|