<p>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.</p>

<p>Use Fourier transforms to improve the complexity to what you need.</p>

CC BY-SA 3.0
2015-11-19T21:54:02.923Z
2015-11-19T21:59:09.590Z
2015-11-19T21:59:09.590Z
Paul
<p>Elaborating <a href="https://cstheory.stackexchange.com/questions/33093/min-hamming-distance-of-a-given-string-from-substrings-of-another-string/33136#33136">Paul's suggestion</a> for a $O(n \log n)$-time algorithm:</p>

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

<p>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:</p>

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

<p>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 <a href="https://en.wikipedia.org/wiki/Cooley%E2%80%93Tukey_FFT_algorithm" rel="nofollow noreferrer">Fast Fourier Transform</a>.</p>

<p>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$.</p>

<p>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)$.</p>

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

<ol>
<li>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 &gt; \mathrm{degree}(r'(z))=O(nm)$.</li>
<li>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.</li>
<li>Compute the values $r'(w_j)=p'(w_j)q'(w_j)$ for all $j$ in $O(\ell)$-time.</li>
<li>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.</li>
</ol>

<p>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]$.</p>

CC BY-SA 3.0
2015-11-21T18:00:33.327Z
2015-11-21T19:26:59.563Z
2017-04-13T12:32:28.077Z
Thomas Steinke
<p>Let <span class="math-container">$U$</span> be a small finite set.
Consider the following problem:</p>
<p><strong>Input:</strong> two strings <span class="math-container">$u \in U^k$</span> and <span class="math-container">$v\in U^n$</span> with <span class="math-container">$k \leq n$</span>.<br />
<strong>Output:</strong> a (contiguous) substring of <span class="math-container">$v$</span> of length <span class="math-container">$k$</span>
with the minimum <a href="https://en.wikipedia.org/wiki/Hamming_distance" rel="nofollow noreferrer">Hamming distance</a> from <span class="math-container">$u$</span>.</p>
<p>In other words I want to compute the following function:
<span class="math-container">$$f(u,v) = \arg\min_{j &lt; n-k} d_H(u, v[j,j+k])$$</span>
where <span class="math-container">$n = |v|$</span> and <span class="math-container">$k = |u|$</span>.</p>
<blockquote>
<p>What is the fastest algorithm for this problem?</p>
<p>Can this problem be solved in time <span class="math-container">$O(n\log n)$</span>?</p>
</blockquote>
<hr />
<p>I think I can solve the problem if I have a data structure as follows:
Let <span class="math-container">$B = \{0, 1 \}$</span> and <span class="math-container">$k \le n$</span> be fixed numbers.
We want a data structure <span class="math-container">$D$</span> with the following properties:</p>
<ul>
<li><p>Build: for <span class="math-container">$v \in B^n$</span> and <span class="math-container">$u \in B^k$</span>, <span class="math-container">$D.Build(v, u)$</span> builds an instance of <span class="math-container">$D$</span> in time <span class="math-container">$O(n \log n)$</span>.</p>
</li>
<li><p>Query: for <span class="math-container">$1 \le q \le n - k + 1$</span>, <span class="math-container">$D.Query(q)$</span> returns <span class="math-container">$\langle u, v[q, q + k - 1]\rangle$</span> in time <span class="math-container">$O(\log n)$</span>.</p>
</li>
</ul>
<blockquote>
<p>Is there a data structure with these properties?</p>
</blockquote>
<p><span class="math-container">$\langle \cdot , \cdot \rangle $</span> is the dot product and
<span class="math-container">$v[i, j]$</span> = <span class="math-container">$(v_i,\ldots, v_{j})$</span> is the subsequence of <span class="math-container">$v$</span> from <span class="math-container">$i$</span> to <span class="math-container">$j$</span>.</p>

CC BY-SA 3.0
2015-11-15T17:55:53.453Z
I suggest you edit your question to focus more on the actual problem you need to solve than trivialities and formalities (I'm sure everyone here knows how to treat strings as vectors and how dot product is defined).

Specifically, it's unclear which of the parameters of your problem are fixed and which are not.

 I've made a lot of assumption to interpret your question, but in any case, have a look [here](http://www1.cs.columbia.edu/~wfan/PAPERS/CSB02DNA.pdf), I think you will find it interesting.
chazisop
CC BY-SA 3.0
2015-11-15T18:34:13.133Z
@chazisop, I made a few edits.
Is it better now?
G H
CC BY-SA 3.0
2015-11-15T19:53:55.843Z
I did some clean up on the question. ps: If you ask me you should just directly ask for the fastest way to find the subsequence of a given vector from another given vector with min Hamming distance in place of asking for a data structure that you can use to solve the problem in the way you have in mind.
Kaveh
CC BY-SA 3.0
2015-11-15T22:39:49.633Z
Do you mean in time $O(2^n \log(2^n))$? you can't even scan the vector $u$ in time $O(n \log n)$ which you state as your desired complexity.
kodlu
CC BY-SA 3.0
2015-11-15T22:48:40.407Z
@kodlu, why?

$v = (v_1, \ldots, v_n)$ we scan in time $O(n)$, $u = (u_1,\ldots,u_n)$ we scan in time $O(k)$ = $O(n)$ because $k \le n$.
G H
CC BY-SA 3.0
2015-11-15T23:00:34.533Z
@Kaveh, sorry you're right of course
kodlu
CC BY-SA 3.0
2015-11-15T23:03:46.833Z
@Kaveh, ok, do you know some algorithm without this data structure?
G H
CC BY-SA 3.0
2015-11-16T01:00:48.707Z
also Min hamming distance and Max dot product need not be equivalent in non binary alphabets.
kodlu
CC BY-SA 3.0
2015-11-16T02:51:45.937Z
@kodlu, yes, but we can for every $u \in U^n$ and $t \in U$ build binary vector $u^t = (\ldots,(u_i == t), \ldots)$. Then we work with $u^t$ and $v^t$, find $<u^t[i,j], v^t>$ and $hamming(u[i,j],v) = k - \sum_t <u^t[i,j], v^t>$.
G H
CC BY-SA 3.0
2015-11-19T21:37:38.880Z
Please note that by fixing k you've made $B^k$ O(1) in size.  In particular, you can generate the entire ball of Hamming radius k and probe a suffix tree of v with its members in O(1) time.  That may not be what you intended.  Edit:  I misread this as seeking minimal alignment.
KWillets
CC BY-SA 3.0
2015-11-19T21:54:45.530Z
Retract my edit comment -- I had looked at the original and noticed that minimality wasn't specified, when in fact it was in the "motivation" section.
KWillets
<ds.algorithms><ds.data-structures><linear-algebra><metrics><edit-distance>
Min Hamming distance of a given string from substrings of another string
G H
# Min Hamming distance of a given string from substrings of another string

(Asked by: username_0 on 2015-11-15)

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](https://en.wikipedia.org/wiki/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$.

**Tags:** ds.algorithms, ds.data-structures, linear-algebra, metrics, edit-distance
> **Comments:**
> **username_1**: I suggest you edit your question to focus more on the actual problem you need to solve than trivialities and formalities (I'm sure everyone here knows how to treat strings as vectors and how dot product is defined).  Specifically, it's unclear which of the parameters of your problem are fixed and which are not.   I've made a lot of assumption to interpret your question, but in any case, have a look [here](http://www1.cs.columbia.edu/~wfan/PAPERS/CSB02DNA.pdf), I think you will find it interesting.  
> **username_0**: @chazisop, I made a few edits. Is it better now?  
> **username_2**: I did some clean up on the question. ps: If you ask me you should just directly ask for the fastest way to find the subsequence of a given vector from another given vector with min Hamming distance in place of asking for a data structure that you can use to solve the problem in the way you have in mind.  
> **username_3**: Do you mean in time $O(2^n \log(2^n))$? you can't even scan the vector $u$ in time $O(n \log n)$ which you state as your desired complexity.  
> **username_0**: @kodlu, why?  $v = (v_1, \ldots, v_n)$ we scan in time $O(n)$, $u = (u_1,\ldots,u_n)$ we scan in time $O(k)$ = $O(n)$ because $k \le n$.  
> **username_3**: @Kaveh, sorry you're right of course  
> **username_0**: @Kaveh, ok, do you know some algorithm without this data structure?  
> **username_3**: also Min hamming distance and Max dot product need not be equivalent in non binary alphabets.  
> **username_0**: @kodlu, yes, but we can for every $u \in U^n$ and $t \in U$ build binary vector $u^t = (\ldots,(u_i == t), \ldots)$. Then we work with $u^t$ and $v^t$, find $<u^t[i,j], v^t>$ and $hamming(u[i,j],v) = k - \sum_t <u^t[i,j], v^t>$.  
> **username_4**: Please note that by fixing k you've made $B^k$ O(1) in size.  In particular, you can generate the entire ball of Hamming radius k and probe a suffix tree of v with its members in O(1) time.  That may not be what you intended.  Edit:  I misread this as seeking minimal alignment.  
> **username_4**: Retract my edit comment -- I had looked at the original and noticed that minimality wasn't specified, when in fact it was in the "motivation" section.  

---

## 2 answers

### Answer by username_6 on 2015-11-21. Score: 6 | Accepted answer

Elaborating [Paul's suggestion](https://cstheory.stackexchange.com/questions/33093/min-hamming-distance-of-a-given-string-from-substrings-of-another-string/33136#33136) 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](https://en.wikipedia.org/wiki/Cooley%E2%80%93Tukey_FFT_algorithm).

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 by username_5 on 2015-11-19. Score: 3

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.


---

