Optimal pattern matching algorithms

Gilles Didier

We study a class of finite state machines, called \defi{$w$-matching machines}, which yield to simulate the behavior of pattern matching algorithms while searching for a pattern $w…