2 ms·
This is about as awesome hackery piece of theoretical computer science as you can get, the first asymptotic improvement to regular expression matching in at lea
by carterschonwald 17y ago
This is about as awesome hackery piece of theoretical computer science as you can get, the first asymptotic improvement to regular expression matching in at least 17 years!
- carterschonwald 17y agoto quote from the paper's abstract, the improvement is 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.