Paper

The Complexity of the Approximate Multiple Pattern Matching Problem for Random Strings

Average-case analysis of algorithms String Pattern Matching Computational Complexity bounds
  • Theory of computation → Formal languages and automata theory
  • Theory of computation → Design and analysis of algorithms
Frédérique Bassino
Université Paris 13, Sorbonne Paris Cité, LIPN, CNRS UMR 7030, 99 av. J.-B. Clément, F-93430 Villetaneuse, France
Homepage
Tsinjo Rakotoarimalala
Université Paris 13, Sorbonne Paris Cité, LIPN, CNRS UMR 7030, 99 av. J.-B. Clément, F-93430 Villetaneuse, France
Homepage
Andrea Sportiello
Université Paris 13, Sorbonne Paris Cité, LIPN, CNRS UMR 7030, 99 av. J.-B. Clément, F-93430 Villetaneuse, France
Orcid
Homepage

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].