Subject: Re: [Boost-bugs] [Boost C++ Libraries] #8392: Too complex regex for boost::regex (perl, extended) isn't so complex
From: Boost C++ Libraries (noreply_at_[hidden])
Date: 2013-04-21 17:17:36
#8392: Too complex regex for boost::regex (perl, extended) isn't so complex
-------------------------------+--------------------------------------------
Reporter: bkalinczuk@⦠| Owner: johnmaddock
Type: Bugs | Status: closed
Milestone: To Be Determined | Component: regex
Version: Boost 1.52.0 | Severity: Problem
Resolution: wontfix | Keywords:
-------------------------------+--------------------------------------------
Comment (by steven_watanabe):
Replying to [comment:5 anonymous]:
> >I checked your example with grep and it had no problem with matching
the largest matching substring. (There wasn't even any delay).
>
> Grep is a completely different beast: it's a DFA meaning the complexity
of matching is O(N). Perl compatible engines are NFA's, and in the worst
case the complexity of obtaining a match is NP-complete, so something like
O(N!) for an N-character string.
That isn't really true. NFA matching is in P. The problem is that a Perl
regular expression cannot necessarily be represented by an NFA. The
representation is similar to an NFA, but it isn't really one.
-- Ticket URL: <https://svn.boost.org/trac/boost/ticket/8392#comment:7> Boost C++ Libraries <http://www.boost.org/> Boost provides free peer-reviewed portable C++ source libraries.
This archive was generated by hypermail 2.1.7 : 2017-02-16 18:50:12 UTC