Today I read a paper titled “New Algorithms for Regular Expression Matching”
The abstract is:
In this paper we revisit the classical regular expression matching problem, namely, given a regular expression R and a string Q, decide if Q matches one of the strings specified by R.