- Authors:
-
-
Brodal, Gerth Stølting
;
Close
0000-0001-9054-915X
Department of Computer Science, Faculty of Science, Aarhus University, Aarhus University - Gasieniec, Leszek
-
Brodal, Gerth Stølting
;
- DOI:
- 10.1007/3-540-61258-0_6
- 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 modified version of the data structure supports the insertion of new strings in amortized time O(m).
- ISBN:
- 9783540612582
- Type:
- Conference paper
- Language:
- English
- Published in:
- Lecture Notes in Computer Science: 7th Annual Symposium, Cpm 96 Laguna Beach, California, June 10–12, 1996 Proceedings, 1996, p. 65-74
- Main Research Area:
- Science/technology
- Publication Status:
- Published
- Series:
- Lecture Notes in Computer Science
- Review type:
- Peer Review
- Conference:
- 7th Annual Symposium Combinatorial Pattern Matching. CPM 1996
- Publisher:
- Springer
- Submission year:
- 1996
- Scientific Level:
- Scientific
- ID:
- 2185867100
Checking for on-site access...
