The Complexity of the Approximate Multiple Pattern Matching Problem for Random Strings
Frédérique Bassino, Tsinjo Rakotoarimalala, Andrea Sportiello · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · 2020
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].