An Algorithm for Estimating All Matches Between Two Strings
Mikhail J. Atallah, Frédéric Chyzak, Philippe Dumas · Purdue e-Pubs (Purdue University System) · 1996
: 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)Conv (M)) where 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. (R'esum'e : tsvp) Unit'e de recherche INRIA Rocquencourt Domaine de Voluceau, Rocquencourt, BP 105, 78153 LE CHESNAY Ced...