I am a bit confused. Somehow I have a problem connecting two problems together. The Closest String problem and the problem of matching with mismatches. They seam to be related but, I fail to see the connection. The Closest String problem is defined as :

 

>Instance: Strings $S_{1},S_{2}...S_{n}$ over alphabet $\Sigma$ of length $L$ each and a non-negative integers $d$ and $n$.
>
>Parameters:  

>1. $n$
>2. $d$

>Question: Is there a string $s$ of length $L$ such that $\delta(s,S_{i})\leq d$ for all $i=1..n$?



Note: $\delta(x,y)\leq d$ is the Hamming distance between $x$ and $y$;

This problem is proven to be NP-complete.

On the other hand we have a problem of matching with mismatches, which is described as:

>The problem of string matching with $d$ mismatches consists of finding all occurrences of a pattern of length $m$ in a text of length $n$ such that in at most $d$ positions the text and the pattern have different symbols. In the following, we assume that $0 < d < m$ and $m\leq n$. 



Landau and Vishkin gave the first (to my knowledge) efficient algorithm to solve this problem in O(kn) time.

Now my question is:

Is matching with mismatches, or can it be seen, as a special parametrized case of the Closest String problem and how is this connection made?


Thank you