Title: 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 $\phi(r) = \max_m \ln(s\, m\, r_m)/m$, the
complexity rate for the string characters to be read by this algorithm is at
most $\kappa_{{}_\textrm{UB}}\, \phi(r)$ for some constant
$\kappa_{{}_\textrm{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_{{}_\textrm{LB}}\, \phi(r)$. This proves the optimality of the
algorithm, improving and correcting previous claims.