Longest common subsequence: Difference between revisions
Content added Content deleted
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
m (Clarified preferNextIndex2 optimization to the Hunt and Szymanski algorithm.) |
||
| Line 573: | Line 573: | ||
// |
// |
||
// Look ahead to the next index2 value to optimize |
// 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 threshold[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 |
||
// |
// of the next shorter LCS at prev(limit): |
||
// |
// |
||
auto |
auto preferNextIndex2 = next(it2) != dq2.rend() && |
||
(limit == threshold.begin() || *prev(limit) < *next(it2)); |
(limit == threshold.begin() || *prev(limit) < *next(it2)); |
||
// |
|||
// Depending on match redundancy, this optimization may reduce the number |
|||
// of Pair allocations by factors ranging from 2 up to 10 or more. |
|||
// |
|||
if (skipIndex2) continue; |
if (skipIndex2) continue; |
||