1 Department of Computer Science, Faculty of Science, Aarhus University, Aarhus University2 Department of Computer Science, Science and Technology, Aarhus University3 unknown4 Department of Computer Science, Science and Technology, Aarhus University
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