RE (tilly) 2: Regular Expression Optimizer

in reply to RE: Regular Expression Optimizer
in thread Regular Expression Optimizer

Actually I think it is NP-Hard. Determining that you have a match is polynomial. Determining that you have the match that you are looking for (which is the difference between .* and .*?) is another story entirely... :-)

Comment on RE (tilly) 2: Regular Expression Optimizer

Replies are listed 'Best First'.
RE: RE (tilly) 2: Regular Expression Optimizer by BlaisePascal (Monk) on Aug 31, 2000 at 02:33 UTC
You may be right... I know that it's been shown that NP-Complete problems can be reduced (in P time) to a Perl regex match. But I don't think the proofs I've seen looked at .* vs. .*?. The constructions used backreferences.	[reply]

In Section Seekers of Perl Wisdom