(a+)+$ 为什么能把 CPU 打满：正则的灾难性回溯

一个看着没问题的写法

要求「整段都是字母 a」，很自然会写成：

^(a+)+$

里面 a+ 匹配一串 a，外面再套一层 + 表示这个分组可以重复。逻辑上它和 ^a+$ 完全等价——但实际跑起来差得远。

测一下（结尾故意放一个不匹配的 X）：

import re, time

pattern = re.compile(r'^(a+)+$')

for n in [20, 22, 24, 26]:
    s = 'a' * n + 'X'
    t = time.time()
    pattern.match(s)
    print(f'{n} 个 a: {time.time() - t:.3f}s')

输出大致是：

20 个 a: 0.03s
22 个 a: 0.12s
24 个 a: 0.48s
26 个 a: 1.92s

每多两个字符，耗时翻四倍。 再加几个字符，就是几十秒、几分钟。

那 2 秒花在哪了

回溯型引擎在匹配失败时，会回头换一种切分方式重试。

拿 aaaa 举例，(a+)+ 可以切成：

(aaaa)
(aaa)(a)
(aa)(aa)
(aa)(a)(a)
(a)(aaa)
(a)(aa)(a)
(a)(a)(aa)
(a)(a)(a)(a)

4 个字符就有 8 种切法，n 个字符是 2^(n−1) 种。

关键在于：引擎只有在试到结尾那一刻，才发现那个 X 匹配不上 $。于是前面所有切法都要一个个试完。这就是灾难性回溯（catastrophic backtracking）。

它不挑语言。Python、Java、PHP、JavaScript 的默认引擎都是回溯型，同一段正则在哪个语言里都能炸。

三个修法，从根上到救急

① 把嵌套量词拆掉

^(a+)+$ 和 ^a+$ 语义等价，后者没有任何回溯风险。

判断方法很直接：看到 (x+)+、(x*)*、(x+)* 这种「量词套量词」，先打一个问号。

② 用原子组或占有量词（语言支持的话）

^(?>a+)+$     原子组：一旦匹配进来就不再回头
^a++$         占有量词：同上

要注意：这两个写法不是所有语言都支持。JavaScript 支持 (?> 但直到较新版本才稳定；POSIX 风格的工具大多不支持。

③ 最简单也最稳：先卡住输入长度

if len(s) > 1000:
    return False

回溯的复杂度是指数级的，而指数级的东西一卡长度就死了。这个方法不需要改正则，也不会因为引擎差异而失效。

一个容易忽略的对比

Go 的 regexp 包用的是 RE2（自动机实现），没有回溯，也就没有这个问题——代价是不支持反向引用和一些高级语法。

所以这不是「谁的正则引擎更好」的问题，是你在灵活性和最坏情况之间怎么选：回溯引擎语法强，但最坏情况不可控；RE2 最坏情况可控，但语法阉割。

如果正则的输入来自外部（用户提交、日志内容、抓来的文本），输入长度和复杂度都不由你控制，这时最坏情况就是会发生的。

落一句

看到嵌套量词，先想一件事：匹配失败的时候，引擎要试多少种切法？

指数级的复杂度往往藏在写法里，不在数据量里。