Wu and Manber, Fuzzy String Matching ( String Search)

Time Complexity

$O(nk \lceil m/w \rceil)$

Space Complexity

$O(ms + k \lceil m/w \rceil)$

(https://dl.acm.org/doi/pdf/10.1145/135239.135244)

Approximate?

Approximate

Approximation Factor: Levensthein Distance = k

Randomized?

No, deterministic

Model of Computation

not mentioned

Year

1992

Reference

https://dl.acm.org/doi/pdf/10.1145/135239.135244