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.

| cite | improve this answer | |
  • $\begingroup$ 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? $\endgroup$ – user6697 Feb 4 '13 at 14:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.