2 ms·

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.

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 7mo ago
It might be possible to use a randomised algorithm to estimate the number of matches in only linear time.