The edit distance problem is a classical fundamental problem in computer
science in general, and in combinatorial pattern matching in particular. The
standard dynamic programming solution for this problem computes the
edit-distance between a pair of strings of total length O(N) in O(N^2) time. To
this date, this quadratic upper-bound has never been substantially improved for
general strings. However, there are known techniques for breaking this bound in
case the strings are known to compress well under a particular compression
scheme.