正则表达式替换的复杂性

取决于实现。什么语言/图书馆/班级？可能有一个最好的情况，但它将非常特定于实现中的功能数量。

从纯粹的理论立场来看：

我熟悉的实现是构建一个确定性有限自动机来识别正则表达式。这是在 O（2^m） 中完成的，m 是正则表达式的大小，使用标准算法。一旦构建好了，通过它运行一个字符串在字符串的长度上是线性的 - O（n），n 是字符串长度。在字符串中找到的匹配项的替换应为常量时间。

所以总的来说，我想 O（2^m + n）。

为了深入研究theprise的答案，对于自动机的构造，O（2^m）是最坏的情况，尽管它实际上取决于正则表达式的形式（对于一个与单词匹配的非常简单的表达式，它是在O（m）中，例如使用Knuth-Morris-Pratt算法）。

您可以通过构建非确定性有限自动机而不是 DFA 来换取空间来换取速度。这可以在线性时间内遍历。当然，在最坏的情况下，这可能需要 O（2^m） 空间。我希望这种权衡是值得的。

取决于正则表达式的定义。如果允许串联、替代和 Kleene-star 的运算符，则时间实际上可以是 ，其中 是正则表达式的大小，是字符串的长度。您可以通过构建一个 NFA（即线性的 ），然后通过维护您所处的状态集并为每个输入字母更新 （in ） 来模拟它。O(m*n+m)mnmO(m)

使正则表达式解析变得困难的因素：

• 括号和反向引用：使用上述算法进行捕获仍然是可以的，尽管它会增加复杂性，因此可能是不可行的。反向引用提高了正则表达式的识别能力，难度很大
• Positive look-Ahead：只是交集的另一个名称，它将上述算法的复杂性提高到O(m^2+n)
• 负展望：构建自动机的灾难（可能是PSPACE完备的）。但是仍然可以使用动态算法来解决，例如O(2^m)O(n^2*m)

请注意，通过具体的实现，事情可能会变得更好或更糟。根据经验，简单的功能应该足够快，并且明确（例如，不像）正则表达式更好。a*a*

其他可能感兴趣的理论信息。

为清楚起见，假设正则表达式的标准定义

http://en.wikipedia.org/wiki/Regular_language

从形式语言理论。实际上，这意味着唯一的建筑物 材料是字母符号、串联、交替和 Kleene 闭包，以及单位和零常数（出现在 群论原因）。一般来说，最好不要使这个术语过载 尽管脚本语言的日常实践导致 歧义。

有一个 NFA 结构可以解决常规的匹配问题 表达式 r 和输入文本 t 在 O（|r| |t|） 时间和 O（|r|） 空间中，其中 |-|是长度函数。迈尔斯进一步改进了该算法

http://doi.acm.org/10.1145/128749.128755

到时间和空间复杂度 O（|r| |t| / log |t|） 通过使用自动机节点列表和四个俄罗斯范式。这种范式似乎是以四个俄罗斯人的名字命名的，他们写了一篇开创性的论文，但事实并非如此 在线。然而，这些计算生物学说明了这种范式 讲义

http://lyle.smu.edu/~saad/courses/cse8354/lectures/lecture5.pdf

我觉得用数字和 作者的国籍，而不是他们的姓氏。

添加反向引用的正则表达式的匹配问题是 NP-complete，由 Aho 证明

http://portal.acm.org/citation.cfm?id=114877

通过从顶点覆盖问题（经典的NP完全问题）进行简化。

为了确定性地将正则表达式与反向引用匹配，我们可以 使用回溯（与 Perl 正则表达式引擎不同）来跟踪 输入文本 t 中可分配给 r.只有 O（|t|^2） 个子词可以分配给任何一个变量 在 R 中。如果 r 中有 n 个变量，则可能有 O（|t|^2n） 作业。一旦固定了对变量的子字符串赋值，则 问题归结为普通的正则表达式匹配。因此， 将正则表达式与反向引用进行匹配的最坏情况复杂度为 O（|t|^2n）。

但请注意，尚未出现具有反向引用的正则表达式 功能齐全的正则表达式。

例如，将“不在乎”符号与其他符号区分开来 运营商。有几种多项式算法决定了一组 模式与输入文本匹配。例如，Kucherov 和 Rusinowitch

http://dx.doi.org/10.1007/3-540-60044-2_46

将模式定义为一个单词 w_1@w_2@...@w_n其中每个w_i都是一个单词（不是正则表达式），而“@”是一个可变长度的“不在乎”符号，不包含在w_i中的任何一个中。它们派生出一个 O（（|t| + |P|）日志 |P|）将一组模式 P 与输入文本 t 匹配的算法，其中 |t|是文本的长度，|P|是 P 中所有单词的长度。

了解这些复杂性度量是如何组合的以及是什么会很有趣 是正则表达式匹配问题的复杂度，其中 回溯引用、“不在乎”和其他实用的有趣功能 正则表达式。

唉，我还没有说过关于Python的一句话...... :)

如果你追求匹配和替换，这意味着分组和反向引用。

下面是一个 perl 示例，其中分组和反向引用可用于解决 NP 完全问题： http://perl.plover.com/NPC/NPC-3SAT.html

这（再加上其他一些理论花絮）意味着使用正则表达式进行匹配和替换是 NP 完备的。

请注意，这与正则表达式的正式定义不同，正则表达式没有分组的概念，并且在多项式时间内匹配，如其他答案所述。

In python's library, even if a regex is compiled, the complexity can still be exponential (in string length) in some cases, as it is not built on DFA. Some references here, here or here.re