Diffing means computing the longest common subsequence (LCS); the edit script is everything that's not part of the LCS. The proposed algorithm greedily finds a matching element. However it may be that it would be better to skip this element, and not incorporate it into your sequence.

Consider the following sequences (here each letter represents a line).

   AAAB
   BAAA

Where the first one is "left" and the second one is "right".

The LCS is AAA. The minimal edit script from left to right is:

1. Insert B at beginning.

2. Delete B at end.

The proposed O(N) algorithm finds B as the first matching line, and thereby exhaust `left`. So it finds the common subsequence of just "B" and its edit script is:

1. Delete 3 As at beginning

2. Insert 3 As at end

which is longer.