求解该正则表达式是如何浪费浏览器的时间的（匹配不可能成功的）： http://jsfiddle.net/ioioio/F2zQP/2/

[jakwings]

Safari 的正则引擎竟然如此不同，正常通过？Chrome 和 Firefox 的正则引擎到底干了什么好事？

假如是 NFA 类型的正则引擎，匹配的时间复杂度不是应该为 O(n^2) 的么？

[momou]

不要用直接量语法试一下

[jakwings]

@momou 改成 /^ {4}[^\n]*(?:\n {4}[^\n]*\n?)*$/ 倒是很快的。但是就是不明白为什么原来的会那么慢（Safari 除外）……

[jakwings]

@jakwings 说错了，改成 /^ {4}[^\n]*(?:\n {4}[^\n]*)*\n?$/ 才是等效的。

[zzNucker]

没那么简单，典型的回溯失控。 你最后的那个末尾匹配符匹配不到的话会从后往前反复逐个匹配，加上前面你的空格又只匹配掉4个，后面就有一大堆字符等着你去反复比较。。。

[zzNucker]

你可以试试把4改大一点或者把末尾匹配去掉。。。

[momou]

var regex = new RegExp("/^(?: {4}[^\n]*\n?)+$/");不会有问题
应该是字符被转义了吧

[zzNucker]

@momou new regexp 里面不要加定界符了。

[jakwings]

@zzNucker 呃，我好像明白了，时间复杂度似乎比 O(n^2) 还高……

重复匹配本身的复杂度就是 O(n^2) ，然后它的每一次重复中的子匹配过程也是 O(n^2) 复杂度，于是复杂度是 O(n^4) ……看来 Safari 的正则引擎干了一些特别的预测。囧

[zzNucker]

@jakwings 对，尤其像你这种里面又有局部能匹配的，最后又整体不能成功的，就在里面反复找来找去，非常耗时间。

[lyric]

大多数动态语言的正则引擎实现为了支持向后引用，都超过了正则文法，因此都不是 NFA 实现

详情可以参考这篇 Paper： http://swtch.com/~rsc/regexp/regexp1.html

[baocaixiong]

一不小心输入了100，浏览器挂了。。。。。

[baocaixiong]

cpu都跑满了。。。

[jakwings]

@lyric 谢了，那个大神的文章很不错～实在是值得收藏啊。

文章里的正则测试 Chrome 还是得用好几秒，Safari 和 Firefox 都瞬间搞定了，看来 Chrome 的正则引擎的优化还不怎么聪明。Safari 的貌似是优化得最好的。Firefox 的「优化」则往往是直接抛出 InternalError ……