News for hackers. Stuff that matters.
Re:Python, Catastrophic Regular Expressions and the GIL (2013) by wikfwikf on Tuesday November 15, 2022 @04:09AM (#33606947)
Why is the run time exponential in the length of the string of a's? It seems like it should be at most O(n^3).

2^n is the number of subsets of the string of a's with no contiguity requirements. Nothing like this number of possible matches should need to be checked. What am I missing?

There are no comments on this comment yet.