It might be possible to use a randomised algorithm to estimate the number of matches in only linear time.