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 modified version of the data structure supports the insertion of new strings in amortized time O(m).
Lecture Notes in Computer Science: 7th Annual Symposium, Cpm 96 Laguna Beach, California, June 10–12, 1996 Proceedings, 1996, p. 65-74