Approximate pattern matching with k-mismatches in packed text

Emanuele Giaquinta, Szymon Grabowski, Kimmo Fredriksson

Given strings $P$ of length $m$ and $T$ of length $n$ over an alphabet of size $\sigma$, the string matching with $k$-mismatches problem is to find the positions of all the substrings i…