Pattern Matching with Mismatches: A Simple Randomized Algorithm and its Analysis
Mikhail J. Atallah, Philippe Jacquet, Wojciech Szpankowski · Purdue e-Pubs (Purdue University System) · 1992
The study and comparison of strings of symbols from a (possibly very large) alphabet is relevant to various areas of computer science.In particular, the problem of finding all positions, in a text string oflength n, at which a pattern string oflength m "almost occurs" is of great practical importance.Here by "almost occurs" we mean that some fixed percentage of the characters of the pattern (for example, 90% of them) are equal to their corresponding characters in the text.In this paper we give an algorithm that (i) has O(nlogm) time complexity, and (ii) computes with high probability all of the almost-occurrences of the pattern in the text irrespective of the probabilistic characteristics of the pattern and text.We use a probabilistic framework to design some parameters of the algorithm.