Subj : Re: String searching with a twist
To   : comp.programming
From : niklasb
Date : Tue Aug 09 2005 03:26 pm


3rdtry@willets.org wrote:
> >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).

We seem to have a difference in terms. By DFA I meant deterministic
finite state automaton, hence no backtracking, hence O(N). I quite
agree that the DFA will have more states than an equivalent NFA
(non-deterministic finite state automaton) might have.

If you read my original post more closely, you'll see that I defined
M as the number of *states* so I stand by a total run time of O(N+M).

Of course one might reasonably ask how M depends on the inputs. It
doesn't depend just on the length of the pattern (the OP's 'm')
because "575" will have more states than "121".

.