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.

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