Longest common subsequence: Difference between revisions

Content added Content deleted
(Resorted to verbose typedef and parameter names to help clarify their purpose.)
m (Clarified naming of the FindLCS() method, traceLCS bool, and chains deque.)
Line 493: Line 493:
typedef deque<INDEXES*> MATCHES;
typedef deque<INDEXES*> MATCHES;


uint32_t Pairs(MATCHES& indexesOf2MatchedByIndex1, shared_ptr<Pair>* pairs) {
uint32_t FindLCS(MATCHES& indexesOf2MatchedByIndex1, shared_ptr<Pair>* pairs) {
auto trace = pairs != nullptr;
auto traceLCS = pairs != nullptr;
PAIRS traces;
PAIRS chains;
THRESHOLD threshold;
THRESHOLD threshold;


Line 528: Line 528:
// divided by factors ranging from 2 up to 10 or more.
// divided by factors ranging from 2 up to 10 or more.
//
//
auto skip = next(it2) != dq2.rend() &&
auto skipIndex2 = next(it2) != dq2.rend() &&
(limit == threshold.begin() || *prev(limit) < *next(it2));
(limit == threshold.begin() || *prev(limit) < *next(it2));
if (skip) continue;
if (skipIndex2) continue;


if (limit == threshold.end()) {
if (limit == threshold.end()) {
// insert case
// Insert Case
threshold.push_back(index2);
threshold.push_back(index2);
// Refresh limit iterator:
// Refresh limit iterator:
limit = prev(threshold.end());
limit = prev(threshold.end());
if (trace) {
if (traceLCS) {
auto prefix = index3 > 0 ? traces[index3 - 1] : nullptr;
auto prefix = index3 > 0 ? chains[index3 - 1] : nullptr;
auto last = make_shared<Pair>(index1, index2, prefix);
auto last = make_shared<Pair>(index1, index2, prefix);
traces.push_back(last);
chains.push_back(last);
}
}
}
}
else if (index2 < *limit) {
else if (index2 < *limit) {
// replacement case
// Update Case
// Update limit value:
*limit = index2;
*limit = index2;
if (trace) {
if (traceLCS) {
auto prefix = index3 > 0 ? traces[index3 - 1] : nullptr;
auto prefix = index3 > 0 ? chains[index3 - 1] : nullptr;
auto last = make_shared<Pair>(index1, index2, prefix);
auto last = make_shared<Pair>(index1, index2, prefix);
traces[index3] = last;
chains[index3] = last;
}
}
}
}
Line 558: Line 559:
} // next index1
} // next index1


if (trace) {
if (traceLCS) {
// Return the LCS as a linked list of matched index pairs:
// Return the LCS as a linked list of matched index pairs:
auto last = traces.size() > 0 ? traces.back() : nullptr;
auto last = chains.size() > 0 ? chains.back() : nullptr;
// Reverse longest back-trace
// Reverse longest chain
*pairs = Pair::Reverse(last);
*pairs = Pair::Reverse(last);
}
}
Line 606: Line 607:
Match(indexesOf2MatchedByChar, indexesOf2MatchedByIndex1, s1, s2);
Match(indexesOf2MatchedByChar, indexesOf2MatchedByIndex1, s1, s2);
shared_ptr<Pair> pairs; // obtain the LCS as index pairs
shared_ptr<Pair> pairs; // obtain the LCS as index pairs
auto length = Pairs(indexesOf2MatchedByIndex1, &pairs);
auto length = FindLCS(indexesOf2MatchedByIndex1, &pairs);
return Select(pairs, length, false, s1, s2);
return Select(pairs, length, false, s1, s2);
}
}
Retrieved from "https://rosettacode.org/wiki/Longest_common_subsequence"