Following yesterday's StackOverflow outage - is regular expression matching really difficult, or is the implementation simply inefficient?

Yesterday StackOverflow was down for half an hour. Later, they wrote a blog post about it, detailing that the problem stemmed from unexpectedly high complexity of regular expression matching.

In short, the regular expression a+b, when running on the string aaaaaaaaaaaaaac, runs in $O(n^2)$ time where $n$ is the number of a characters, because it uses backtracking.

You can reproduce the issue with the following Python code, which on my computer, takes over 4 seconds to run:

import re, time
start = time.time()
re.findall(r'\s+$', ' '*20000 + 'x') print(time.time() - start) This was very surprising to me; I'd have thought that a regex matcher works more efficiently, e.g. by constructing a DFA from the regex and then running the wanted string through it, which I'd have thought would be$O(n)$(not including the DFA construction). (For instance, the book Introduction to Algorithms by Cormen, Leiserson, Rivest goes through a similar algorithm on the way to introducing the Knuth-Morris-Pratt algorithm). My question: Is there something inherently difficult in regular expression matching that does not allow an$O(n)$algorithm, or are we simply talking about an inefficient implementation (in Python, in whatever StackOverflow uses, etc.)? • There's an article about this. I think it's here but the server's down at the time of writing. The executive summary is that, yes, if you're just doing literal regular expressions such as the one that caused the problem here, you can match in linear time by compiling to an automaton though, for interpreted languages, you need to consider the time the compilation takes and if it's really worth doing that. – David Richerby Jul 21 '16 at 9:51 • Can this regex be rewritten to become faster? I mean do on really have to go down to substr functions or he can just think up better regex? I'm talking exactly about this one /\s+$/ on (" "*20000)+"x" – Nakilon Jul 29 '16 at 2:00