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

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

[{'answer_id': 21675, 'author': 'Chris', 'author_id': 2134, 'author_profile': 'https://Stackoverflow.com/users/2134', 'pm_score': 1, 'selected': False, 'text': '<p>Depends on the implementation.  What language/library/class?  There may be a best case, but it would be very specific to the number of features in the implementation.</p>\n'}, {'answer_id': 21702, 'author': 'goric', 'author_id': 940, 'author_profile': 'https://Stackoverflow.com/users/940', 'pm_score': 5, 'selected': True, 'text': '<p>From a purely theoretical stance:</p>\n\n<p>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.</p>\n\n<p>So overall, I suppose O(2^m + n).</p>\n'}, {'answer_id': 28628, 'author': 'OysterD', 'author_id': 2638, 'author_profile': 'https://Stackoverflow.com/users/2638', 'pm_score': 2, 'selected': False, 'text': '<p>To delve into theprise\'s answer, for the construction of the automaton, O(2^m) is the worst case, though it really depends on the form of the regular expression (for a very simple one that matches a word, it\'s in O(m), using for example the <a href="http://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm" rel="nofollow noreferrer">Knuth-Morris-Pratt algorithm</a>).</p>\n'}, {'answer_id': 43204, 'author': 'Pramod', 'author_id': 1386292, 'author_profile': 'https://Stackoverflow.com/users/1386292', 'pm_score': 0, 'selected': False, 'text': "<p>You can trade space for speed by building a nondeterministic finite automaton instead of a DFA. This can be traversed in linear time. Of course, in the worst case this could need O(2^m) space. I'd expect the tradeoff to be worth it.</p>\n"}, {'answer_id': 766514, 'author': 'jpalecek', 'author_id': 51831, 'author_profile': 'https://Stackoverflow.com/users/51831', 'pm_score': 3, 'selected': False, 'text': "<p>Depends on what you define by regex. If you allow operators of concatenation, alternative and Kleene-star, the time can actually be <code>O(m*n+m)</code>, where <code>m</code> is size of a regex and <code>n</code> is length of the string. You do it by constructing a NFA (that is linear in <code>m</code>), and then simulating it by maintaining the set of states you're in and updating that (in <code>O(m)</code>) for every letter of input.</p>\n\n<p>Things that make regex parsing difficult:</p>\n\n<ul>\n<li>parentheses and backreferences: capturing is still OK with the aforementioned algorithm, although it would get the complexity higher, so it might be infeasable. Backreferences raise the recognition power of the regex, and its difficulty is well</li>\n<li>positive look-ahead: is just another name for intersection, which raises the complexity of the aforementioned algorithm to <code>O(m^2+n)</code></li>\n<li>negative look-ahead: a disaster for constructing the automaton (<code>O(2^m)</code>, possibly PSPACE-complete). But should still be possible to tackle with the dynamic algorithm in something like <code>O(n^2*m)</code></li>\n</ul>\n\n<p>Note that with a concrete implementation, things might get better or worse. As a rule of thumb, simple features should be fast enough, and unambiguous (eg. not like <code>a*a*</code>) regexes are better.</p>\n"}, {'answer_id': 883610, 'author': 'Community', 'author_id': -1, 'author_profile': 'https://Stackoverflow.com/users/-1', 'pm_score': 3, 'selected': False, 'text': '<p>Other theoretical info of possible interest.</p>\n\n<p>For clarity, assume the standard definition for a regular expression</p>\n\n<p><a href="http://en.wikipedia.org/wiki/Regular_language" rel="noreferrer">http://en.wikipedia.org/wiki/Regular_language</a></p>\n\n<p>from the formal language theory. Practically, this means that the only building\nmaterial are alphabet symbols, operators of concatenation, alternation and\nKleene closure, along with the unit and zero constants (which appear for\ngroup-theoretic reasons). Generally it\'s a good idea not to overload this term\ndespite the everyday practice in scripting languages which leads to\nambiguities.</p>\n\n<p>There is an NFA construction that solves the matching problem for a regular\nexpression r and an input text t in O(|r| |t|) time and O(|r|) space, where\n|-| is the length function. This algorithm was further improved by Myers</p>\n\n<p><a href="http://doi.acm.org/10.1145/128749.128755" rel="noreferrer">http://doi.acm.org/10.1145/128749.128755</a></p>\n\n<p>to the time and space complexity O(|r| |t| / log |t|) by using automaton node listings and the Four Russians paradigm. This paradigm seems to be named after four Russian guys who wrote a groundbreaking paper which is not\nonline. However, the paradigm is illustrated in these computational biology\nlecture notes</p>\n\n<p><a href="http://lyle.smu.edu/~saad/courses/cse8354/lectures/lecture5.pdf" rel="noreferrer">http://lyle.smu.edu/~saad/courses/cse8354/lectures/lecture5.pdf</a></p>\n\n<p>I find it hilarious to name a paradigm by the number and\nthe nationality of authors instead of their last names.</p>\n\n<p>The matching problem for regular expressions with added backreferences is\nNP-complete, which was proven by Aho</p>\n\n<p><a href="http://portal.acm.org/citation.cfm?id=114877" rel="noreferrer">http://portal.acm.org/citation.cfm?id=114877</a></p>\n\n<p>by a reduction from the vertex-cover problem which is a classical NP-complete problem.</p>\n\n<p>To match regular expressions with backreferences deterministically we could\nemploy backtracking (not unlike the Perl regex engine) to keep track of the\npossible subwords of the input text t that can be assigned to the variables in\nr. There are only O(|t|^2) subwords that can be assigned to any one variable\nin r. If there are n variables in r, then there are O(|t|^2n) possible\nassignments. Once an assignment of substrings to variables is fixed, the\nproblem reduces to the plain regular expression matching. Therefore the\nworst-case complexity for matching regular expressions with backreferences is\nO(|t|^2n).</p>\n\n<p>Note however, regular expressions with backreferences are not yet\nfull-featured regexen.</p>\n\n<p>Take, for example, the "don\'t care" symbol apart from any other\noperators. There are several polynomial algorithms deciding whether a set of\npatterns matches an input text. For example, Kucherov and Rusinowitch</p>\n\n<p><a href="http://dx.doi.org/10.1007/3-540-60044-2_46" rel="noreferrer">http://dx.doi.org/10.1007/3-540-60044-2_46</a></p>\n\n<p>define a pattern as a word w_1@w_2@...@w_n where each w_i is a word (not a regular expression) and "@" is a variable length "don\'t care" symbol not contained in either of w_i. They derive an O((|t| + |P|) log |P|) algorithm for matching a set of patterns P against an input text t, where |t| is the length of the text, and |P| is the length of all the words in P.</p>\n\n<p>It would be interesting to know how these complexity measures combine and what\nis the complexity measure of the matching problem for regular expressions with\nbackreferences, "don\'t care" and other interesting features of practical\nregular expressions.</p>\n\n<p>Alas, I haven\'t said a word about Python... :)</p>\n'}, {'answer_id': 942602, 'author': 'Dave', 'author_id': 65833, 'author_profile': 'https://Stackoverflow.com/users/65833', 'pm_score': 0, 'selected': False, 'text': '<p>If you\'re after matching and substitution, that implies grouping and backreferences.  </p>\n\n<p>Here is a perl example where grouping and backreferences can be used to solve an NP complete problem:\n  <a href="http://perl.plover.com/NPC/NPC-3SAT.html" rel="nofollow noreferrer">http://perl.plover.com/NPC/NPC-3SAT.html</a></p>\n\n<p>This (coupled with a few other theoretical tidbits) means that using regular expressions for matching and substitution is NP-complete.</p>\n\n<p>Note that this is different from the formal definition of a regular expression - which don\'t have the notion of grouping - and match in polynomial time as described by the other answers.</p>\n'}, {'answer_id': 63529950, 'author': 'Peter Franek', 'author_id': 1119629, 'author_profile': 'https://Stackoverflow.com/users/1119629', 'pm_score': 0, 'selected': False, 'text': '<p>In python\'s <code>re</code> 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 <a href="https://stackoverflow.com/questions/63527560/exponential-running-time-for-simple-python-regex?noredirect=1#comment112337609_63527560">here</a>, <a href="https://swtch.com/%7Ersc/regexp/regexp1.html" rel="nofollow noreferrer">here</a> or <a href="https://www.regular-expressions.info/catastrophic.html" rel="nofollow noreferrer">here</a>.</p>\n'}]
['https://Stackoverflow.com/questions/21669', 'https://Stackoverflow.com', 'https://Stackoverflow.com/users/1448/']