Is matching with mismatches a special(parametrized) case of Closest String problem?

Question

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: $n,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?

Answer 1

In the latter you are given the string $s$ that you are looking for in the former.

An algorithm for the first one is to search for a string $s$ (try all strings) and run the latter procedure and verify that the set you get is the entire set.