The Complexity of the Approximate Multiple Pattern Matching Problem for Random Strings
- Theory of computation → Formal languages and automata theory
- Theory of computation → Design and analysis of algorithms
Abstract. We describe a multiple string pattern matching algorithm which is well-suited for approximate search and dictionaries composed of words of different lengths. We prove that this algorithm has optimal complexity rate up to a multiplicative constant, for arbitrary dictionaries. This extends to arbitrary dictionaries the classical results of Yao [SIAM J. Comput. 8, 1979], and Chang and Marr [Proc. CPM94, 1994].