Faster Regular Expression Matching

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