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