News for hackers. Stuff that matters.

A comment on Is there a regular expression to detect a valid regular expression?. Parent comment

Re:Is there a regular expression to detect a valid regular e... by ridiculous_fish on Sunday September 08, 2019 @05:44PM (#20913637)
Does "linear wrt A and linear wrt B" mean O(A*B) or O(A+B)?
[ Parent | on HN ]
Re:Is there a regular expression to detect a valid regular e... by gpm on Sunday September 08, 2019 @05:53PM (#20913682)
It means O(AB), but is carefully worded to not say (or suggest) it's not possible to do O(A+B) which is a subset of O(AB) ;)

I'm not sure if it's possible to match regex with that time complexity, it looks like the implementation I referenced is O(AB). https://docs.rs/regex/1.3.1/regex/#untrusted-input.

(star symbol removed because hn decided to turn them into a block of italics)

[ Parent | on HN ]