Designing optimal- and fast-on-average pattern matching algorithms

Gilles Didier, Laurent Tichit

Given a pattern $w$ and a text $t$, the speed of a pattern matching algorithm over $t$ with regard to $w$, is the ratio of the length of $t$ to the number of text accesses performe…