# Approximate Dictionary Queries

In * Proc. 7th Annual Symposium on Combinatorial Pattern Matching*, volume 1075 of * Lecture Notes in Computer Science*, pages 65-74. Springer Verlag, Berlin, 1996.

## 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*(*n**m*) 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*(*n**m*). 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**

10.1007/3-540-61258-0_6

**BIBT**_{E}X entry

@incollection{cpm96,
author = "Gerth St{\o}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"
}