The k-mappability problem revisited

Abstract

The $k$-mappability problem has two integers parameters $m$ and $k$. For every subword of size $m$ in a text $S$, we wish to report the number of indices in $S$ in which the word occurs with at most $k$ mismatches. The problem was lately tackled by Alzamel et al. For a text with constant alphabet $\Sigma$ and $k\in O(1)$, they present an algorithm with linear space and $O(n{\log }^{k+1}n)$ time. For the case in which $k=1$ and a constant size alphabet, a faster algorithm with linear space and $O(n\log (n)\log \log (n))$ time was presented in a 2020 paper by Alzamel et al. In this work, we enhance the techniques of Alzamel et al.'s 2020 paper to obtain an algorithm with linear space and $O(n\log (n))$ time for $k=1$. Our algorithm removes the constraint of the alphabet being of constant size. We also present linear algorithms for the case of $k=1$, $|\Sigma |\in O(1)$ and $m=\Omega (\sqrt{n})$.