Re: PHP 4.0 Bug #5545: regular expression matching goes into almost infinite loop

Thanks a lot for the quick feedback. $text can be several thousand characters because it is a whole web page. I have looked at "Mastering Regular Expressions" and I see that constructs like .* can cause exponential time usage because of backtracking. I was assuming that the PHP regular expression implementation would be fast over big strings, like egrep, and that it should achieve the theoretical worst-case time complexity, which is O(mn) I believe, where m is the length of the regexpr and n is the length of the string, $text in this case. Just to confirm, does PHP use a non-POSIX NFA implementation of regexprs? Is a DFA implementation available, to achieve better worst-case speed? The book "Professional PHP Programming" doesn't discuss these issues at all. It uses examples like ereg ("^.+@.+\\..+$", $str) and ereg("^([0-9]+).(.*)$", $line, &$data) so I assumed this was reasonable... Charles On Tue, 11 Jul 2000, Rasmus Lerdorf wrote: > How big is $text? > > Try preg_match() instead. > > -Rasmus > > On 13 Jul 2000 elkan@cs.ucsd.edu wrote: > > > From: elkan@cs.ucsd.edu > > Operating system: Mandrake Linux 7.0r2 > > PHP version: 4.0 Release Candidate 2 > > PHP Bug Type: Scripting Engine problem > > Bug description: regular expression matching goes into almost infinite loop > > > > I am using 4.0.0 with Apache 1.3.12 and MySQL, all standard. > > The following code works fine: > > > > $tpattern = ".*<big><b>(.*)</b></big>"; > > if (eregi($tpattern,$text,$match)) { > > $title = $match[1]; > > > > But adding .* at the end of the pattern, making > > > > $tpattern = ".*<big><b>(.*)</b></big>.*"; > > > > can take 41 seconds to run, measured using time(). > > Sometimes it gives the error message > > Fatal error: Maximum execution time of 30 seconds > > exceeded in /home/elkan/public_html/crawler.php on line 58 > > > > > > > >