Efficient Matching with Memoization for Regexes with Look-around and Atomic Grouping (Extended Version)

Hiroya Fujinami, Ichiro Hasuo

Regular expression (regex) matching is fundamental in many applications, especially in web services. However, matching by backtracking -- preferred by most real-world implementatio…