###
FIX to Bit-Parallel Witnesses and their Applications to Approximate String
Matching

#### Level: Small

There is an error in line -5 of page 11 (in the version of the paper linked
from this site). We say that, since *a* >= 1/*s*, it holds that
*l* >= 3 log_*s* *m* is a sufficient condition (where *s*
is called "sigma" in the paper). Unfortunately the inequality should be
*a* <= 1/*s* for this to hold.
Fortunately, the result is still valid. Since *a*
= 1/(*s*^(1-*A*) *A*^(2*A*) (1-*A*)^(2(1-*A*))),
being *A* called "alpha" in the paper, and the method works for
*A* < 1/2, and the formula is maximized for *A* = 1/2, it holds
1/*s* <= *a* <= 4/sqrt(*s*), and hence
log(1/*a*) = Theta(log *s*).