Hacker News new | ask | show | jobs
by dpkendal 4007 days ago
Not true. Finite automata (NFAs, DFAs) can match that pattern (and any pattern that doesn't involve backreferences or lookaround) in O(n) time where n is the size of the input string. DFA implementations are worst-case O(n ^ 2) in the number of states of the regular expression, but this is far better in most cases than the exponential worst-case time in terms of the input string offered by backtracking implementations.

See https://swtch.com/~rsc/regexp/ for information on finite-state-machine implementations of regexp matching.
1 comments
thaumasiotes 4007 days ago
> DFA implementations are worst-case O(n ^ 2) in the number of states of the regular expression

What? Why is that? If the NFA has n states, then the DFA in principle might need one state for every possible set of states the NFA might be in, of which there are 2^n. Where does n^2 come from?

link
dpkendal 4007 days ago
My mistake, I meant O(2 ^ n) indeed. Regardless, having exponential time complexity in terms of the regular expression (which is usually controlled by the programmer) where the processing is done at compile-time is much better than having exponential complexity in terms of the input string (which often comes from an untrusted source) where the processing is done at run-time.
link