Michael Haggerty <mhag...@alum.mit.edu> writes: > So if `N ≫ M`, there is necessarily a lot of repetition among the `N + > M` lines that the hunk could possibly overlay. Specifically, it must > consist of `floor((N + M)/M)` identical copies of the hunk, plus > possibly a few leftover lines constituting the start of another repetition. > > Given this large amount of repetition, it seems to me that there is > never a need to scan more than the bottom `M + 1` possible positions [1] > plus the highest possible position [2] to be sure of finding the very > best one. In the pathological case that you described above, where `M` > is 1, only three positions have to be evaluated, not 100.
Nicely analysed.
