在工程实践中，我们常常讨论正则表达式的性能优化：DFA 与 NFA 的区别、贪心与非贪心的选择、回溯机制的规避。然而，这些讨论大多聚焦于引擎的实现层面，忽略了一个根本性的理论问题：是否存在一个理论下界，约束了所有正则引擎在全匹配场景下的时间复杂度？答案是肯定的 —— 无论采用何种底层实现，只要满足左最长（leftmost-longest）语义并输出全部匹配结果，正则匹配在最坏情况下的复杂度必然是 Ω(mn²)，其中 m 为模式长度，n 为文本长度。本文将从理论层面给出严格证明，并探讨其对工程决策的启示。

问题定义：全匹配与单机匹配的根本差异

在讨论正则匹配复杂度之前，必须明确我们讨论的是哪一种查询语义。正则匹配存在两种核心模式：单机匹配（single match）和全匹配（all matches）。单机匹配只需回答 “文本中是否存在匹配”，找到第一个匹配后即可终止；全匹配则需要枚举并报告文本中所有满足模式的子串。

对于单机匹配，经典理论已经给出明确答案：通过模拟确定有限自动机（DFA）或非确定有限自动机（NFA），可以在 O (m+n) 时间内完成判定，其中 m 为正则表达式的大小，n 为文本长度。这一结论独立于引擎的具体实现 —— 无论是基于 NFA 的回溯引擎（如 JavaScript 的 RegExp），还是基于 DFA 的确定性匹配（如 awk 的实现），单机匹配在最坏情况下都不会超过线性时间。

然而，全匹配的场景发生了根本性变化。当我们要求引擎报告所有匹配时，问题从 “是否存在” 转变为 “找出每一个”，这一语义变化带来了理论复杂度的质变。即使内部使用高效的 DFA，全匹配仍可能退化为二次方时间。下文将通过严格的理论构造证明这一下界。

形式化模型与语义假设

为给出严谨的理论证明，我们需要明确模型假设。设正则表达式 R 的长度为 m，文本 T 的长度为 n。我们假设引擎满足以下两条语义约束，这两条约束在实际生产环境中几乎所有主流引擎都默认遵循：

第一条语义是左最长匹配（leftmost-longest matching），也称为 POSIX 语义。当正则表达式包含分支操作符 |（或）时，如果多个分支都能匹配同一位置，引擎应选择匹配长度最长的子表达式；若长度相同，则选择最左侧的分支。这一语义保证了匹配结果的一致性和可预测性，是工业界的事实标准。

第二条语义是全量枚举（exhaustive enumeration）。引擎需要输出文本中所有不重叠的匹配项，每找到一个匹配后从匹配结束位置之后继续搜索，直到文本末尾。这与许多实际应用场景相符 —— 如日志分析中的多模式提取、代码扫描中的规则匹配等。

在上述语义约束下，我们可以构造一个具体的输入实例，证明任意正则引擎在全匹配模式下都必然面临二次方时间复杂度。

构造性证明：正则 .*a|b 与文本 b^n 的二次方陷阱

考虑正则表达式 R = .*a|b 和文本 T = b^n（即连续 n 个字符 b 组成的字符串）。我们逐位置分析引擎的行为，证明其时间复杂度必为 Ω(n²)。

在位置 0 处，引擎首先尝试分支 .*a。由于文本中不存在字符 a，. 将贪婪地扫描整个剩余后缀 T [0..n)，检查每一个字符是否为 a，直至末尾才确认匹配失败。这一扫描过程消耗 O (n) 时间。随后，引擎尝试分支 b，成功匹配单个字符 b，输出一个长度为 1 的匹配。

引擎随后将搜索起点推进到位置 1，重复上述过程：在 T [1..n) 上尝试 .*a 失败（耗时 O (n-1)），然后匹配 b。这一过程对每个起始位置 i（0 ≤ i < n）都会发生。总的字符扫描次数为：

(n) + (n-1) + (n-2) + … + 1 = n(n+1)/2 = Θ(n²)

即使我们忽略正则表达式本身的处理成本（每步还有 O (m) 的常数因子），仅凭这一构造就能得到 Ω(n²) 的时间下界。关键在于：二次方复杂度并非来自回溯或糟糕的实现，而是来自左最长语义与全量枚举的必然交互。每个起始位置都必须完整扫描剩余后缀以确定哪个分支最长，而这种扫描在所有 n 个起始位置上累加，形成了三角求和。

需要特别强调的是，这一构造并不依赖于特定的引擎实现。无论是基于 NFA 的回溯引擎（如 PCRE、Python re），还是基于 DFA 的确定性引擎（如 Google RE2、Docker grep），只要它们输出全匹配并遵循左最长语义，就必须执行上述扫描过程。DFA 可以在单机匹配中避免回溯，但在全匹配场景下，外层的起始位置循环与内层的 suffix 扫描之间的交互同样产生了二次方成本。

理论下界的形式化表述

基于上述构造，我们可以给出更一般性的理论陈述：对任意正则表达式 R 和文本 T，在左最长语义下输出全部匹配的最坏情况时间复杂度为 Ω(mn²)。这一下界是严格的 —— 它不仅存在于特定输入上，而且是理论上无法逾越的鸿沟。

直觉论证如下：在最坏情况下，文本中每个位置都可能是某个匹配的起点，这意味着起始位置的候选集合大小为 Θ(n)。对于每个起始位置，左最长语义可能要求引擎检查长度为 Θ(n) 的后缀，才能确定最终选择哪个分支或确认无匹配。两个 Θ(n) 级别的因子相乘，得到 Ω(n²) 的理论下界。值得注意的是，这一结论与正则表达式的大小 m 无关（除非 m 极大以至于影响常数因子），因此更精确的表述是 Ω(mn²) 或 Ω(n²)。

这一理论下界为工程实践提供了明确的边界认知：任何正则引擎在全匹配场景下都无法承诺优于二次方的渐近时间复杂度，除非修改语义假设 —— 例如只输出第一个匹配、限制贪婪量化的范围、或采用启发式近似。

与工程实践的区隔：为何理论下界不等于引擎评测

理解理论下界与工程实践的区别至关重要。理论下界证明的是最坏情况下的不可避免性，而非平均情况或特定输入下的实际表现。在实际工作负载中，大多数正则匹配可能运行得很快，因为输入文本不一定会触发上述构造的病态场景。然而，这并不能否认二次方复杂度的存在 —— 它像一条不可逾越的墙壁，存在于可能性空间中。

主流正则引擎在工程层面做了大量优化：RE2 使用了基于 Thompson NFA 的确定性模拟，避免了回溯；Ripgrep 在底层调用了 Rust 的 regex crate，通过 SIMD 加速和_literals 优化显著降低了常数因子；PCRE2 提供了 JIT 编译选项，将热路径编译为机器码。这些优化可以有效降低二次方行为在实际场景中的触发概率和常数开销，但无法改变理论下界本身。

对工程师而言，理论下界的价值在于决策指导。当业务场景要求在超大规模文本上进行正则全匹配时，应意识到纯正则方法可能存在性能瓶颈，考虑结合预过滤（如使用更快的 exact-match 子串进行粗筛）、分块处理、或专用领域语言（DSL）等方式规避最坏情况。理解理论的边界，才能在优化时不至于南辕北辙。

结论

本文从理论层面严格证明了正则表达式全匹配在左最长语义下必然面临 Ω(mn²) 的时间下界。通过构造正则 .*a|b 与文本 b^n 的具体实例，我们展示了二次方复杂度是如何从语义本质中诞生的，而非来自特定引擎的实现缺陷。这一结论与具体实现无关 —— 无论是回溯型 NFA 还是确定性 DFA，都无法绕过这一理论约束。

理解这一理论边界，有助于工程师在系统设计阶段做出更明智的技术选型，并在性能调优时设定合理的预期。正则表达式是强大的工具，但它的能力边界同样值得敬畏。

参考资料

  • Stack Overflow: Complexity of Regex substitution — 讨论了全匹配场景下的二次方复杂度来源
  • Ilya Evdokimov: "All Longest Regex Matches in Linear Time" — 指出在左最长语义下无法避免 O (mn²) 时间