Longest common subsequence: Difference between revisions

Content added Content deleted
m (changed l/r to match scs task (same output))
(The reverse iterator it2 now visits index2 values in descending order.)
Line 389: Line 389:
auto dq2 = *it1;
auto dq2 = *it1;
auto limit = threshold.end();
auto limit = threshold.end();
for (auto it2 = dq2.begin(); it2 != dq2.end(); it2++) {
for (auto it2 = dq2.rbegin(); it2 != dq2.rend(); it2++) {
// Each of the index1, index2 pairs considered here correspond to a match
// Each of the index1, index2 pairs considered here correspond to a match
auto index2 = *it2;
auto index2 = *it2;


//
//
// Note: The index2 values are monotonically decreasing, which allows the
// Note: The reverse iterator it2 visits index2 values in descending order,
// thresholds to be updated in-place. Monotonicity allows a binary search,
// allowing thresholds to be updated in-place. std::lower_bound() is used
// implemented here by std::lower_bound().
// to perform a binary search.
//
//
limit = lower_bound(threshold.begin(), limit, index2);
limit = lower_bound(threshold.begin(), limit, index2);
Line 410: Line 410:
// 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.end() &&
auto skip = next(it2) != dq2.rend() &&
(limit == threshold.begin() || *prev(limit) < *next(it2));
(limit == threshold.begin() || *prev(limit) < *next(it2));
if (skip) continue;
if (skip) continue;
Line 463: Line 463:
uint32_t index = 0;
uint32_t index = 0;
for (const auto& it : s2)
for (const auto& it : s2)
indexes[it].push_front(index++);
indexes[it].push_back(index++);


for (const auto& it : s1) {
for (const auto& it : s1) {
Retrieved from "https://rosettacode.org/wiki/Longest_common_subsequence"