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.)?