News for hackers. Stuff that matters.

A comment on A Regular Expression Matcher (2007). Parent comment

Re:A Regular Expression Matcher (2007) by user2994cb on Friday February 14, 2020 @08:10AM (#22326168)
An FSA matcher will be O(M) - one state transition per input character.
[ Parent | on HN ]
Re:A Regular Expression Matcher (2007) by jstimpfle on Friday February 14, 2020 @12:16PM (#22328227)
If you're looking at a specific regex (~FSA), then N is constant... If you have a function that runs an arbitrary regex, then N will vary.
[ Parent | on HN ]