We give a randomized algorithm for estimating the score vector of matches between a text string of length~$N$ and a pattern string of length~$M$; this is the vector obtained when the pattern is slid along the text, and the number of matches is counted for each position. The randomized algorithm takes deterministic time $O( (N / M ) {\textstyle {\it Conv}} (M) )$ where ${\textstyle {\it Conv}} (M)$ is the time for performing a convolution of two vectors of size $M$ each. The algorithm finds an unbiased estimator of the scores, whose variance is particularly small for scores that are close to $M$, i.e., for approximate occurrences of the pattern in the text. No assumptions are made about the probabilistic characteristics of the input, or about the number of different symbols appearing in $T$ or $P$ (i.e., the alphabet size need not be much smaller than $M$). The solution extends to the weighted case and to higher dimensions.