In practice, it doesn't make sense to fill in the whole table.
Instead, consider a limited window (size k) at any one time.
Not optimal, since might be more than k added or deleted lines.
Works well in practice, and brings running time down to O(nk).
