News for hackers. Stuff that matters.

A comment on The quadratic problem nobody fixed. Parent comment

Re:The quadratic problem nobody fixed by hyperpape on Monday March 23, 2026 @10:06PM (#47497839)
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.

[ Parent | on HN ]
Re:The quadratic problem nobody fixed by ogogmad on Tuesday March 24, 2026 @05:41AM (#47500379)
It might be possible to use a randomised algorithm to estimate the number of matches in only linear time.
[ Parent | on HN ]