Match-finding does not need to be quadratic. However, truly optimal gzip block splitting is very slow, indeed.