Longest common subsequence: Difference between revisions
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> INDEXES;
typedef unordered_map<char, INDEXES> CHAR_TO_INDEXES_MAP;
Line 535 ⟶ 534:
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
//
Line 545 ⟶ 544:
if (!it1->empty()) {
auto dq2 = *it1;
auto limit =
for (auto it2 = dq2.rbegin(); it2 != dq2.rend(); it2++) {
// Each
auto index2 = *it2;
//
// Note: The reverse iterator it2 visits index2 values in descending order,
// allowing
//
//
limit = lower_bound(
auto index3 = distance(
//
// 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
// superseded on the next index2 iteration.
//
// Verify
//
//
auto preferNextIndex2 = next(it2) != dq2.rend() &&
(limit ==
//
Line 576 ⟶ 575:
if (preferNextIndex2) continue;
if (limit ==
// Insert Case
// Refresh limit iterator:
limit = prev(
if (traceLCS) {
auto prefix = index3 > 0 ? chains[index3 - 1] : nullptr;
Line 610 ⟶ 609:
}
auto length =
return length;
}
|