Which Regular Expression Patterns are Hard to Match?

Open benibela opened this issue 8 years ago • 1 comments

I just came across this paper https://arxiv.org/abs/1511.07070 listing lower and upper bounds for regex patterns.

Does FLRE reach the optimum runtime for every case?

Their new algorithm for matching (foo|bar|123|etc)* could speed things up?

Jan 31 '17 21:01 benibela

Hey, look a follow up: https://arxiv.org/abs/1611.00918

With an even faster algorithm for (foo|bar|123|etc)*

Apr 18 '17 16:04 benibela