如何掌握正则表达式这一开发利器，看这篇就够了( 二 ) _正则表达式

在尝试了所有可能的分步方法后宣告该问题没有答案

在最坏的情况下，回溯法会导致一次复杂度为指数时间的计算。

3.2 什么是正则回溯正则引擎主要可以分为两大类：一种是 DFA(Deterministic finite automaton 确定型有穷自动机) ，另一种是 NFA（NFA Non-deterministic finite automaton非确定型有穷自动机）。NFA 速度较 DFA 更慢，并且实现复杂，但是它又有着比 DFA 强大的多的功能，比如支持反向引用等。像 JAVAScript、java、php、Python、c#等语言的正则引擎都是 NFA 型， NFA 正则引擎的实现过程中使用了回溯。
3.2.1 没有回溯的正则举一个网上常见的例子，正则表达式/ab{1,3}c/g 去匹配文本'abbc' ，我们接下来会通过 RegexBuddy 分析其中的匹配过程，后续的一个章节有关于 RegexBuddy 的使用介绍。

文章插图

如上图所示，让我们一步一步分解匹配过程：

正则引擎先匹配 a 。
正则引擎尽可能多地(贪婪)匹配 b 。
正则引擎匹配 c ，完成匹配。

在这之中，匹配过程都很顺利，并没发生意外(回溯) 。
3.2.2 有正则回溯的正则让我们把上面的正则修改一下， /ab{1,3}c/g 改成/ab{1,3}bc/g ，接下再通过 RegexBuddy 查看分析结果。

文章插图

我们再一步一步分解匹配过程：

正则引擎先匹配 a 。
正则引擎尽可能多地(贪婪)匹配 b{1,3}中的 b 。
正则引擎去匹配 b ，发现没 b 了，糟糕！赶紧回溯！
返回 b{1,3}这一步，不能这么贪婪，少匹配个 b 。
正则引擎去匹配 b 。
正则引擎去匹配 c ，完成匹配。

以上，就是一个简单的回溯过程。
3.3 正则回溯的几种常见形式从上面发生正则回溯的例子可以看出来，正则回溯的过程就是一个试错的过程，这也是回溯算法的精髓所在。回溯会增加匹配的步骤，势必会影响文本匹配的性能，所以，要想提升正则表达式的匹配性能，了解回溯出现的场景(形式)是非常关键的。
3.3.1 贪婪量词在 NFA 正则引擎中，量词默认都是贪婪的。当正则表达式中使用了下表所示的量词，正则引擎一开始会尽可能贪婪的去匹配满足量词的文本。当遇到匹配不下去的情况，就会发生回溯，不断试错，直至失败或者成功。
量词说明a*0 or morea+1 or morea?0 or 1a{5}exactly fivea{2,}two or morea{1,3}between one & three
当多个贪婪量词挨着存在，并相互有冲突时，秉持的是"先到先得"的原则，如下所示：

let string = "12345";let regex = /(d{1,3})(d{1,3})/;console.log( string.match(regex) );// => ["12345", "123", "45", index: 0, input: "12345"]

3.3.2 惰性量词贪婪是导致回溯的重要原因，那我们尽量以懒惰匹配的方式去匹配文本，是否就能避免回溯了呢？答案是否定的。
让我们还是看回最初的例子， /ab{1,3}c/g 去匹配 abbc 。接下来，我们再把正则修改一下，改成/ab{1,3}?c/g 去匹配 abbc ，以懒惰匹配的方式去匹配文本， RegexBuddy 执行步骤如下图所示：