The complexity of the Multiple Pattern Matching Problem for random strings

Frédérique Bassino, Tsinjo Rakotoarimalala, Andrea Sportiello

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 alpha…