Min Hamming distance of a given string from substrings of another string

Question

Let $U$ be a small finite set. Consider the following problem:

Input: two strings $u \in U^k$ and $v\in U^n$ with $k \leq n$.
Output: a (contiguous) substring of $v$ of length $k$ with the minimum Hamming distance from $u$.

In other words I want to compute the following function: $$f(u,v) = \arg\min_{j < n-k} d_H(u, v[j,j+k])$$ where $n = |v|$ and $k = |u|$.

What is the fastest algorithm for this problem?

Can this problem be solved in time $O(n\log n)$?

---

I think I can solve the problem if I have a data structure as follows: Let $B = \{0, 1 \}$ and $k \le n$ be fixed numbers. We want a data structure $D$ with the following properties:

• Build: for $v \in B^n$ and $u \in B^k$, $D.Build(v, u)$ builds an instance of $D$ in time $O(n \log n)$.

• Query: for $1 \le q \le n - k + 1$, $D.Query(q)$ returns $\langle u, v[q, q + k - 1]\rangle$ in time $O(\log n)$.

Is there a data structure with these properties?

$\langle \cdot , \cdot \rangle $ is the dot product and $v[i, j]$ = $(v_i,\ldots, v_{j})$ is the subsequence of $v$ from $i$ to $j$.

Answer 1

Elaborating Paul's suggestion for a $O(n \log n)$-time algorithm:

Input: Let $u \in [m]^k$ and $v \in [m]^n$ with $k \leq n$, where $U=[m]=\{1,2,\cdots,m\}$.

Define polynomials $$p(x,y) = \sum_{i \in [n]} x^i y^{v_i} \qquad \text{and} \qquad q(x,y) = \sum_{j \in [k]} x^{k-j} y^{m-u_j}.$$ Compute the polynomial $$r(x,y) = p(x,y) q(x,y).$$ Then $$r(x,y) = \sum_{t,s} x^t y^s \left|\left\{ (i,j) \in [n]\times[k] : i+k-j=t \wedge v_i + m - u_j =s \right\}\right|. $$ In particular, for $k \leq t \leq n$, the coefficient of $x^{t} y^m$ in $r(x,y)$ is $$\left|\left\{ (i,j) \in [n]\times[k] : i=j+t-k \wedge v_i = u_j\right\}\right| = k-d_H(u,v[t-k+1,t]).$$ Thus, the coefficients of $r(x,y)$ provide a lookup table for $d_H(u,v[t-k+1,t])$ for $k \leq t \leq n$. So, given the coefficients of $r(x,y)$, we can easily solve the problem by picking the $t$ such that $x^{t}y^m$ has the largest coefficient:

Output: $f(u,v)+k=\mathrm{arg}\max_{k \leq t \leq n} \mathrm{coefficient}_{r(x,y)}(x^{t}y^m)$

So how fast is this algorithm? I claim it can be implemented in $O(nm \log (nm))$ time (assuming arithmetic operations with $O(\log (nm))$ bits of precision take constant time) using the Fast Fourier Transform.

The core of the problem is computing $r(x,y)=p(x,y)q(x,y)$, where the degree of $p(x,y)$ is at most $n$ in $x$ and $m$ in $y$ and the degree of $q(x,y)$ is at most $k$ in $x$ and $m$ in $y$.

We can first reduce it to univariate polynomial multiplication by defining $$p'(z) = p(z^{m+1},z) \qquad \text{and} \qquad q'(z)=q(z^{m+1},z),$$ computing $r'(z)=p'(z)q'(z)$, and then extracting $r(x,y)$ from the identity $r'(z)=r(z^{m+1},z)$.

I won't go through the FFT algorithm (even though it's one of my favourite algorithms), but the general idea is:

1. Pick $\ell = O(nm)$ special points $w_1, \cdots, w_\ell \in \mathbb{C}$, namely $w_j=\exp(2\pi\sqrt{-1}j/\ell)$ and $\ell$ is a power of $2$ with $\ell > \mathrm{degree}(r'(z))=O(nm)$.
2. Evaluate $p'(w_j)$ and $q'(w_j)$ for all $j \in [\ell]$ in $O(\ell \log \ell)$-time using a divide and conquer algorithm.
3. Compute the values $r'(w_j)=p'(w_j)q'(w_j)$ for all $j$ in $O(\ell)$-time.
4. Interpolate the coefficients of $r'(z)$ from the values $r'(w_j)$ in $O(\ell \log \ell)$-time using essentially the same divide and conquer algorithm.

The observation that makes the divide and conquer algorithm work is that we can write $p'(z) = p'_\text{even}(z^2) + z \cdot p'_\text{odd}(z^2)$, where $p'_\text{even}$ and $p'_\text{odd}$ have half the degree of $p'$. It then suffices to recursively evaluate $p'_\text{even}(w_{2j})$ and $p'_\text{odd}(w_{2j})$ for $j \in [\ell/2]$.

Answer 2

Hint: Express the binary vectors as a polynomial with coefficients in {-1,0,1} and obtain the hamming distance of u with all length k contiguous subsequences of v through a polynomial multiplication.

Use Fourier transforms to improve the complexity to what you need.