正则表达式之灾难性回溯

在《贪婪与非贪婪的匹配原理》 一文中我们可以了解 回溯 的原理；这个回溯其实埋着危险： 灾难性回溯catastrophic backtracking

      正则表达式1：(a+)*

       正则表达式2：(a+)*s

这两个正则表达式看上去很相似，第二个仅仅是要求最后必须匹配为s。

 我们再分别用两个不同的字符串来匹配。

        input1：aaaaaaaaas

        input2：aaaaaaaaab

        匹配结果应该是显而易见的：

        正则表达式1和input1匹配：true 

        正则表达式1和input2匹配：true

        正则表达式2和input1匹配：true

        正则表达式2和input2匹配：false

上述是匹配结果，是没有问题的。我们关注的，是操作时间。上述四种组合的匹配时间，基本上都在1ms的级别。

但是，我们把第四种匹配组合中，匹配字符串input2修改一下，input2为10个字符，我们将它修改成20个字符：

aaaaaaaaaaaaaaaaaaaab  运行时间变成113ms

继续将它修改成30个字符：

aaaaaaaaaaaaaaaaaaaaaaaaaaaaab  在运行过程中，已经很清楚，出现灾难了，运行时间为111231ms

这就是正则表达式的灾难性回溯。在进行匹配的时候，匹配引擎在前面的a字符的时候，匹配成功，到达b的时候，匹配失败，就会进行回溯【即从第二个a开始再来一遍】，而回溯的数量，和之前匹配的数量呈指数的增长趋势。

那么怎么解决这种问题的出现？  无解， 是的， 只能说尽量不要使用复杂的正则表达式，或者在正则之前对表达式进行一些先行判断或者处理；