[zzazzdsa]

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.

[starikovskaya]

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.