Longest common subsequence: Difference between revisions

Content added Content deleted
m (→‎{{header|BASIC}}: It's QuickBASIC, not BASIC in general.)
(Renamed prefixEnd deque. Improved preferNextIndex2 comment.)
Line 527: Line 527:


typedef deque<shared_ptr<Pair>> PAIRS;
typedef deque<shared_ptr<Pair>> PAIRS;
typedef deque<uint32_t> THRESHOLD;
typedef deque<uint32_t> INDEXES;
typedef deque<uint32_t> INDEXES;
typedef unordered_map<char, INDEXES> CHAR_TO_INDEXES_MAP;
typedef unordered_map<char, INDEXES> CHAR_TO_INDEXES_MAP;
Line 535: Line 534:
auto traceLCS = pairs != nullptr;
auto traceLCS = pairs != nullptr;
PAIRS chains;
PAIRS chains;
THRESHOLD threshold;
INDEXES prefixEnd;


//
//
//[Assert]After each index1 iteration threshold[index3] is the least index2
//[Assert]After each index1 iteration prefixEnd[index3] is the least index2
// such that the LCS of s1[0:index1] and s2[0:index2] has length index3 + 1
// such that the LCS of s1[0:index1] and s2[0:index2] has length index3 + 1
//
//
Line 545: Line 544:
if (!it1->empty()) {
if (!it1->empty()) {
auto dq2 = *it1;
auto dq2 = *it1;
auto limit = threshold.end();
auto limit = prefixEnd.end();
for (auto it2 = dq2.rbegin(); it2 != dq2.rend(); it2++) {
for (auto it2 = dq2.rbegin(); it2 != dq2.rend(); it2++) {
// Each of the index1, index2 pairs considered here correspond to a match
// Each index1, index2 pair corresponds to a match
auto index2 = *it2;
auto index2 = *it2;


//
//
// Note: The reverse iterator it2 visits index2 values in descending order,
// Note: The reverse iterator it2 visits index2 values in descending order,
// allowing thresholds to be updated in-place. std::lower_bound() is used
// allowing in-place update of prefixEnd[]. std::lower_bound() is used to
// to perform a binary search.
// perform a binary search.
//
//
limit = lower_bound(threshold.begin(), limit, index2);
limit = lower_bound(prefixEnd.begin(), limit, index2);
auto index3 = distance(threshold.begin(), limit);
auto index3 = distance(prefixEnd.begin(), limit);


//
//
// Look ahead to the next index2 value to optimize Pairs used by the Hunt
// Look ahead to the next index2 value to optimize Pairs used by the Hunt
// and Szymanski algorithm. If the next index2 is also an improvement on
// and Szymanski algorithm. If the next index2 is also an improvement on
// the value currently held in threshold[index3], a new Pair will only be
// the value currently held in prefixEnd[index3], a new Pair will only be
// superseded on the next index2 iteration.
// superseded on the next index2 iteration.
//
//
// Verify the next value of index2 will be greater than the final element
// Verify that a next index2 value exists; and that this value is greater
// of the next shorter LCS at prev(limit):
// than the final index2 value of the LCS prefix at prev(limit):
//
//
auto preferNextIndex2 = next(it2) != dq2.rend() &&
auto preferNextIndex2 = next(it2) != dq2.rend() &&
(limit == threshold.begin() || *prev(limit) < *next(it2));
(limit == prefixEnd.begin() || *prev(limit) < *next(it2));


//
//
Line 576: Line 575:
if (preferNextIndex2) continue;
if (preferNextIndex2) continue;


if (limit == threshold.end()) {
if (limit == prefixEnd.end()) {
// Insert Case
// Insert Case
threshold.push_back(index2);
prefixEnd.push_back(index2);
// Refresh limit iterator:
// Refresh limit iterator:
limit = prev(threshold.end());
limit = prev(prefixEnd.end());
if (traceLCS) {
if (traceLCS) {
auto prefix = index3 > 0 ? chains[index3 - 1] : nullptr;
auto prefix = index3 > 0 ? chains[index3 - 1] : nullptr;
Line 610: Line 609:
}
}


auto length = threshold.size();
auto length = prefixEnd.size();
return length;
return length;
}
}
Retrieved from "https://rosettacode.org/wiki/Longest_common_subsequence"