Selective Memoization for Efficient Backtracking Regular Expression Matching

Martin Berglund, Brink van der Merwe, Iain le Roux

Backtracking regular expression matchers are widely used due to their expressive power but may exhibit exponential worst-case matching time. Memoization provides a principled metho…