Rosetta Code

Longest common subsequence: Difference between revisions

Page Discussion

Longest common subsequence (view source)

Revision as of 08:19, 22 April 2023

43 bytes removed ,  1 year ago
Renamed prefixEnd deque. Improved preferNextIndex2 comment.
m (→‎{{header|BASIC}}: It's QuickBASIC, not BASIC in general.)
(Renamed prefixEnd deque. Improved preferNextIndex2 comment.)
Line 527:
 
typedef deque<shared_ptr<Pair>> PAIRS;
typedef deque<uint32_t> THRESHOLD;
typedef deque<uint32_t> INDEXES;
typedef unordered_map<char, INDEXES> CHAR_TO_INDEXES_MAP;
Line 535 ⟶ 534:
auto traceLCS = pairs != nullptr;
PAIRS chains;
THRESHOLDINDEXES thresholdprefixEnd;
 
//
//[Assert]After each index1 iteration thresholdprefixEnd[index3] is the least index2
// such that the LCS of s1[0:index1] and s2[0:index2] has length index3 + 1
//
Line 545 ⟶ 544:
if (!it1->empty()) {
auto dq2 = *it1;
auto limit = thresholdprefixEnd.end();
for (auto it2 = dq2.rbegin(); it2 != dq2.rend(); it2++) {
// Each of the index1, index2 pairs considered herepair correspondcorresponds to a match
auto index2 = *it2;
 
//
// Note: The reverse iterator it2 visits index2 values in descending order,
// allowing thresholds to be updated in-place update of prefixEnd[]. std::lower_bound() is used to
// to perform a binary search.
//
limit = lower_bound(thresholdprefixEnd.begin(), limit, index2);
auto index3 = distance(thresholdprefixEnd.begin(), limit);
 
//
// 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
// the value currently held in thresholdprefixEnd[index3], a new Pair will only be
// superseded on the next index2 iteration.
//
// Verify thethat a next value of index2 willvalue beexists; greaterand thanthat thethis finalvalue elementis greater
// ofthan the nextfinal shorterindex2 value of the LCS prefix at prev(limit):
//
auto preferNextIndex2 = next(it2) != dq2.rend() &&
(limit == thresholdprefixEnd.begin() || *prev(limit) < *next(it2));
 
//
Line 576 ⟶ 575:
if (preferNextIndex2) continue;
 
if (limit == thresholdprefixEnd.end()) {
// Insert Case
thresholdprefixEnd.push_back(index2);
// Refresh limit iterator:
limit = prev(thresholdprefixEnd.end());
if (traceLCS) {
auto prefix = index3 > 0 ? chains[index3 - 1] : nullptr;
Line 610 ⟶ 609:
}
 
auto length = thresholdprefixEnd.size();
return length;
}
CNHume
159

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/340727"