The complexity of the Multiple Pattern Matching Problem for random strings

Abstract

We generalise a multiple string pattern matching algorithm, recently proposed by Fredriksson and Grabowski [J. Discr. Alg. 7, 2009], to deal with arbitrary dictionaries on an alphabet of size $s$. If $r_m$ is the number of words of length $m$ in the dictionary, and $\varphi (r)={\max }_m\ln (sm{r}_m)/m$, the complexity rate for the string characters to be read by this algorithm is at most ${\kappa }_{{}_{\text{UB}}}\varphi (r)$ for some constant ${\kappa }_{{}_{\text{UB}}}$. On the other side, we generalise the classical lower bound of Yao [SIAM J. Comput. 8, 1979], for the problem with a single pattern, to deal with arbitrary dictionaries, and determine it to be at least ${\kappa }_{{}_{\text{LB}}}\varphi (r)$. This proves the optimality of the algorithm, improving and correcting previous claims.

25 pages, 4 figures