[hyperpape]

Returning no results is going to be linear in any DFA or NFA based implementation, though. You go character by character, and confirm that there are no matches.

It's only when you return multiple matches that the engines have a problem and become superlinear.

[ogogmad]

It might be possible to use a randomised algorithm to estimate the number of matches in only linear time.