Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
up vote 1 down vote accepted

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.

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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