# Faster Regular Expression Matching

## Philip Bille, DTU

#### Tuesday 25 May 2010 at 15:00-16:00 DIKU, Universitetsparken, room N030

 Abstract: Regular expression matching is a key task (and often the computational bottleneck) in a variety of widely used software tools and applications, for instance, the \texttt{unix} \texttt{grep} and \texttt{sed} commands, scripting languages such as \texttt{awk} and \texttt{perl}, programs for analyzing massive data streams, etc. We show how to solve this ubiquitous task in linear space and \$O(nm(\log \log n)/(\log n)^{3/2} + n + m)\$ time where \$m\$ is the length of the expression and \$n\$ the length of the string. This is the first improvement for the dominant \$O(nm/\log n)\$ term in Myers' \$O(nm/\log n + (n + m)\log n)\$ bound [JACM 1992]. We also get improved bounds for external memory.

Scientific host: Fritz Henglein Administrative host:Renée Korver Michan. All are welcome.
The Copenhagen Programming Language Seminar (COPLAS) is a collaboration between DIKU, ITU and RUC.