[pjscott]

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]

Thanks! Though I imagine in most cases the regular expression itself would be a fixed part of the codebase and not given as input.