News for hackers. Stuff that matters.

A comment on Yes, all longest regex matches in linear time is possible. Parent comment

Re:Yes, all longest regex matches in linear time is possible by ieviev on Wednesday March 18, 2026 @08:53AM (#47425193)
Sorry, finished the post just now with more comparisons on other inputs

The reason is just that the normal mode is faster in average non pathological cases

[ Parent | on HN ]
Re:Yes, all longest regex matches in linear time is possible by tracnar on Wednesday March 18, 2026 @09:38AM (#47425677)
Could you have a heuristics based on the input size and the pattern to decide what to use?
[ Parent | on HN ]
Re:Yes, all longest regex matches in linear time is possible by ieviev on Wednesday March 18, 2026 @09:39AM (#47425685)
Yes, this is entirely possible. you can even explore the automaton eagerly and detect if it's possible to loop from an accepting state to a nonaccepting one.

Exciting stuff for future work

[ Parent | on HN ]
Re:Yes, all longest regex matches in linear time is possible by nextaccountic on Wednesday March 18, 2026 @05:59PM (#47431938)
Ripgrep does something like thhis. It has a meta regex engine that switches engine when it finds what looks like pathological cases (or rather, the regex-automata crate does, which is used by the regex crate, which powers ripgrep).

https://docs.rs/regex-automata/latest/regex_automata/meta/st...

Ripgrep in turn exposes some knobs to tweak the heuristics

https://github.com/BurntSushi/ripgrep/blob/master/FAQ.md#how...

[ Parent | on HN ]