Почему так /? (+) +Q$/.test("XXXXXXXXXXXXXXXXXXXXXXXXXXXX?)?

Question

Когда я бегу

/^(.+)+Q$/.test("XXXXXXXXXXXXXXXXXXXXXXXXXXXXXX") 

в Chrome или IE, она занимает ~ 10 секунд. (Firefox может оценить его почти мгновенно.)

Почему так долго? (И почему/как Firefox может сделать это так быстро?)

(Конечно, я никогда не запускаю это конкретное регулярное выражение, но я сталкиваюсь с аналогичной проблемой с URL-адресом регулярного выражения в http://daringfireball.net/2010/07/improved_regex_for_matching_urls, и, похоже, сводится к этому, то есть определенные URL-адрес, которые будут вызывать браузер запирать)

Например:

var re = /\b((?:https?:\/\/|www\d{0,3}[.]|[a-z0-9.\-]+[.][a-z]{2,4}\/)(?:[^\s()<>]+|\(([^\s()<>]+|(\([^\s()<>]+\)))*\))+(?:\(([^\s()<>]+|(\([^\s()<>]+\)))*\)|[^\s`!()\[\]{};:'".,<>?«»“”‘’]))/i; 
re.test("http://google.com/?q=(AAAAAAAAAAAAAAAAAAAAAAAAAAAAA") 

Answer 1

Как указано thg435, это звучит как катастрофическое обратное отслеживание. Там отличная статья об этом, Regular Expression Matching Can Be Simple And Fast.

В нем описывается эффективный подход, известный как Thompson NFA. Как уже отмечалось, это не поддерживает все функции современных регулярных выражений. Например, он не может делать обратные ссылки. Однако, как это было предложено в статье:.

«Тем не менее, было бы разумно использовать НКУ моделирование Томпсона для наиболее регулярных выражений, и только выявить возвраты когда Требовался особенно умна реализация могла бы объединить два, прибегают к обратному слежению только для размещения обратных ссылок ».

Я подозреваю, что Firefox может это сделать.