なぜ/^(.+)+Q$/.test("XXXXXXXXXXXXXXXXXXXXXXXXXXXXXX "）が長くかかるのですか？

Question

私はクロムやIEに

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

を実行し、それが完了するまでに約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として知られている効率的な手法を記述しています。しかし、これは現代の正規表現のすべての機能をサポートしているわけではありません。たとえば、逆参照はできません。しかし、記事で示唆したよう：

「たとえそうだとしても、 ほとんどの正規表現をトンプソンのNFAのシミュレーションを使用するのが妥当だろう、それは が必要なときだけ後戻りを引き出す特に巧妙な実装では、組み合わせることができ。 2つは バックリファレンスに対応するためだけにバックトラックに頼っています。

私はFirefoxはこれをやってすることができると思います。