News for hackers. Stuff that matters.

A comment on The quadratic problem nobody fixed. Parent comment

Re:The quadratic problem nobody fixed by ieviev on Tuesday March 24, 2026 @06:20AM (#47500621)
It's still O(n * m). The matches are non-overlapping, even if you run a separate engine on the matches post-match it will at most traverse the full input once across all matches.
[ Parent | on HN ]
Re:The quadratic problem nobody fixed by mjmas on Thursday March 26, 2026 @07:13AM (#47529058)
Ture, I forgot about the non-overlapping matchss and that that will cancel out any extra n parameter.

Actually rereading again, it almost seems like it should be possible to do the matching as a special case of the Thompson/Pike VMs and have it loop back around to the start, and deduplicate multiples, but I am only speculating.

[ Parent | on HN ]