# Computing Simultaneous Hamming Neighborhood for a Set of Strings

Let $S = \lbrace s_1, s_2 \ldots s_n \rbrace$ be a set of strings each of length $k$ from an alphabet $\Sigma$, $h(s_i, s_j)$ denote the hamming distance between two strings. The simultaneous hamming neighborhood is defined as $N_{\alpha} = \lbrace s' | h(s',s_j) \leq \alpha, \forall s_j \in S , s' \in \Sigma^k \rbrace$, $1\leq \alpha \leq k$.

I would like to know if this problem (i.e. computing $N_{\alpha}$ efficiently) has been considered earlier ? -- By efficiently I mean the running time of the algorithm should be something like $O(|N_{\alpha}|)$, when $|N_{\alpha}|$ is much larger than $n$.

Thank you very much for your help.

• Hello Tsuyoshi, Thank you for that reference its useful. However I'm interested in the complexity when $k$ is a fixed constant. Thank you, Vamsi. – Infinite Emptiness Jul 18 '11 at 23:53
• @Tsuyoshi: $\Sigma$ is part of input, so any bivariate polynomial in $n$ and $\Sigma$ would be efficient. On the other hand if $\Sigma$ were to be constant I'm wondering if exists is an $O(|N_{\alpha}|)$ algorithm. – Infinite Emptiness Jul 19 '11 at 0:44