Representing Pattern Matching Algorithms by Polynomial-Size Automata

Tobias Marschall, Noemi E. Passing

Pattern matching algorithms to find exact occurrences of a pattern $S\in {\Sigma }^m$ in a text $T\in {\Sigma }^n$ have been analyzed extensively with respect to asymptotic best, worst, and average…