1

Abstract. Given a set of n binary strings of length m each. We consider the problem of answering d{queries. Given a binary query string of length m, a d{query is to report if there exists a string in the set within Hamming distance d of . We present a data structure of size O(nm) supporting 1{queries in time O(m) and the reporting of all strings within Hamming distance 1 of in time O(m). The data structure can be constructed in time O(nm). A slightly modied version of the data structure supports the insertion of new strings in amortized time O(m)