Re: [Boost-bugs] [Boost C++ Libraries] #8392: Too complex regex for boost::regex (perl, extended) isn't so complex

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.