On 13/04/2012, Connor Lane Smith <c...@lubutu.com> wrote: > On 13 April 2012 16:37, Strake <strake...@gmail.com> wrote: >> True, if we trim the start and finish lazily > > That depends on the diff format. diff -e, for example, could work well.
I meant to trim pre-diff, so it would be quadratic in a lesser argument. >> but worst-case diff >> algorithm space usage is worse — quadratic, if I'm not mistaken. > > That's true. Although, diff is worst-case quadratic in the number of > lines, not bytes. True for line-by-line diff, e.g. Unix diff, though the algorithm is more general. > And the fact is the worst-case can be avoided: we > don't really *need* the longest common subsequence, only an > approximation to it. If we exceed some threshold we can simply > 'plump'. You mean, to terminate the subsequence, and start afresh? > To be clear, I don't mean to dismiss either existing situ, this would > just be nice to have as well. Noted. Cheers, strake
