[Top] [All Lists]

Re: Complexity of :matches ?

2005-07-12 04:36:52

I, Philip Guenther <guenther+mtafilters(_at_)sendmail(_dot_)com> wrote:
For an NFA, the setup is O(N) in time and space and matching is O(N*M).

For a non-lazy DFA, the matching is O(M), but the worst-case setup is

I should note that the dragon book's statements, as I tried to
summarize above, are only true of the original, truly regular
"regular expressions" and not the extended or 'irregular' regular
expressions seen in most tools.

In particular, counted repetitions ({n,m}) have to be expanded when
figuring the 'N' of the size of the regexp, while back-references
(\digit) are, IIRC, worst-case exponential to match.  If you're
capturing matches then the POSIX matching rules apparently are
worst-case exponential on the number of characters in the regexp,
or something like that.

Philip Guenther

<Prev in Thread] Current Thread [Next in Thread>