正则表达式替换的复杂性 [英] Complexity of Regex substitution

问题描述

我在任何地方都没有得到答案。正则表达式匹配和替换的运行时复杂性是什么？

I didn't get the answer to this anywhere. What is the runtime complexity of a Regex match and substitution?

编辑：我在python中工作。但想大致了解大多数流行的语言/工具（java，perl，sed）。

I work in python. But would like to know in general about most popular languages/tools (java, perl, sed).

推荐答案

从纯理论上讲立场：

我熟悉的实现是建立一个确定性有限自动机来识别正则表达式。使用标准算法在O（2 ^ m）中完成，m为正则表达式的大小。一旦构建完成，通过它运行的字符串的长度就是线性的-O（n），n是字符串的长度。

The implementation I am familiar with would be to build a Deterministic Finite Automaton to recognize the regex. This is done in O(2^m), m being the size of the regex, using a standard algorithm. Once this is built, running a string through it is linear in the length of the string - O(n), n being string length. A replacement on a match found in the string should be constant time.

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

So overall, I suppose O(2^m + n).

这篇关于正则表达式替换的复杂性的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！