Subj : Re: String searching with a twist
To   : comp.programming
From : 3rdtry
Date : Mon Aug 08 2005 02:05 pm

>Running the DFA is O(N).

It's more than O(N).  Try scanning this:  1111111111.....1.  However I
think a larger DFA would handle the scan in O(N), but it would have
more than O(M) states; the total complexity would then be something
like O(N+M^2) or O(N+2^M).

.