A probabilistic analysis of a pattern matching problem
Mikhail J. Atallah, Philippe Jacquet, Wojciech Szpankowski · Random Structures and Algorithms · 1993
Abstract The study and comparison of strings of symbols from a finite or an infinite alphabet is relevant to various areas of science, notably molecular biology, speech recognition, and computer science. In particular, the problem of finding the minimum “distance” between two strings (in general, two blocks of data) is of a practical importance. In this article we investigate the (string) pattern matching problem in a probabilistic framework, namely, it is assumed that both strings form an independent sequences of i.i.d. symbols. Given a text stringaof lengthnand a pattern stringbof lengthm, letMm,nbe the maximum number of matches betweenband allm‐substrings ofa. Our main probabilistic result shows that for a wide range of input parameters in probability (pr.) providedm, n→∞ such that logn=o(m), wherePis the probability of a match between any two symbols of these strings, andTis the probability of a match between two positions in the text string and a given position of the pattern string. We also prove thatMm,n/m→P almost surely(a.s.) for logn=o(m). © 1993 John Wiley & Sons. Inc.