Fast entropy-bounded string dictionary look-up with mismatches

Paweł Gawrychowski, Gad M. Landau, Tatiana Starikovskaya

We revisit the fundamental problem of dictionary look-up with mismatches. Given a set (dictionary) of $d$ strings of length $m$ and an integer $k$, we must preprocess it into a dat…