to 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 whe

to 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.