gliese1337 / fast-myers-diff

MIT License
53 stars 8 forks source link

`lcs` yields a 4-element triple with zero substring length #20

Open TomBinford opened 3 months ago

TomBinford commented 3 months ago

The first array yielded from lcs is sometimes 4 elements long and has 0 length. The 4-element arrays aren't terrible, I suppose, because the values at index 0/1/2 have the same meaning as they would in a 3-element array. But AFAIK zero-length common substrings are meaningless in the LCS and should be left out. In my testing it seems like this always occurs unless the inputs have a common prefix.

Some examples:

console.log(Array.from(lcs("abc", "abc")));  // good, [ [ 0, 0, 3 ] ]
console.log(Array.from(lcs("abc", "def")));  // bad,  [ [ 0, 3, 0, 3 ] ]
console.log(Array.from(lcs("abc", "bc")));   // bad,  [ [ 0, 1, 0, 0 ], [ 1, 0, 2 ] ]
console.log(Array.from(lcs("abc", "axx")));  // good, [ [ 0, 0, 1 ] ]