In Proc. 7th Annual Symposium on Combinatorial Pattern Matching, volume 1075 of Lecture Notes in Computer Science, pages 65-74. Springer Verlag, Berlin, 1996.
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).
Copyright notice© Springer-Verlag Berlin Heidelberg 1996. All rights reserved.
Online version
cpm96.pdf (197 Kb)
DOI
BIBTEX entry
@incollection{cpm96,
author = "Gerth Stølting Brodal and Leszek G{\c{a}}sieniec",
booktitle = "Proc. 7th Annual Symposium on Combinatorial Pattern Matching",
doi = "10.1007/3-540-61258-0_6",
isbn = "978-3-540-61258-2",
pages = "65-74",
publisher = "Springer {V}erlag, Berlin",
series = "Lecture Notes in Computer Science",
title = "Approximate Dictionary Queries",
volume = "1075",
year = "1996"
}