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

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?

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.
• Are you saying that this is a verifier for the Closest String problem and can be used to show that Closest String problem $\in$ NP? – user6697 Feb 4 '13 at 14:24