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. > 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. 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'. To be clear, I don't mean to dismiss either existing situ, this would just be nice to have as well. cls
