3 ms·
You’re right, of course, but there was a minor miscommunication: the exponential space is exponentially proportional to the size of the regular expression, and
by pjscott 1y ago
You’re right, of course, but there was a minor miscommunication: the exponential space is exponentially proportional to the size of the regular expression, and the linear time is linearly proportional to the length of the string being searched through.
- dullcrisp 1y agoThanks! Though I imagine in most cases the regular expression itself would be a fixed part of the codebase and not given as input.