> I might be wildly misreading the code, but it seems like [1,2,3,a,b,c] diffed with [a,b,c,1,2,3] is going to appear as six lines of replacement.
A bit of a pickle.
The challenge I experienced with this is that either there are 6 changes (line for line comparison) or there are 3 lines the same and three lines moved, but three lines moved means a deletion of 3 lines from the first sample and 3 lines of insertion later in the second sample, which is still 6 differences. The output reads very differently, but the number of differences is identical, which is no change in precision.
Unless my understanding of things is wrong, I'm pretty sure that unless the strong exponential time hypothesis (essentially, n variable CNF-SAT takes O(2^n) time in the worst case) is false, no diff algorithm can run in subquadratic time. If you could, then you would be able to solve longest common subsequence in subquadatic time, and that in turn implies SETH being false by https://arxiv.org/abs/1501.07053 .
I'm pretty sure exact diff in subquadratic time is therefore impossible. It's still a nice heuristic though.
Minor remark: If the edit distance between two n-length strings is (relatively) small, it is possible to find it in subquadratic time. More precisely, if the edit distance is at most d, you can solve the problem in O(nd) time. The upper bound d does not have to be known in advance. The conditional lower bound you mentioned holds only for large values of edit distance.
A bit of a pickle.
The challenge I experienced with this is that either there are 6 changes (line for line comparison) or there are 3 lines the same and three lines moved, but three lines moved means a deletion of 3 lines from the first sample and 3 lines of insertion later in the second sample, which is still 6 differences. The output reads very differently, but the number of differences is identical, which is no change in precision.