Projects per year
Abstract
We consider the problem of dictionary matching in a stream. Given a set of strings, known as a dictionary, and a stream of characters arriving one at a time, the task is to report each time some string in our dictionary occurs in the stream. We present a randomised algorithm which takes O(log log(k + m)) time per arriving character and uses O(k log m) words of space, where k is the number of strings in the dictionary and m is the length of the longest string in the dictionary.
Original language | English |
---|---|
Title of host publication | Algorithms – ESA 2015 |
Subtitle of host publication | 23rd Annual European Symposium, Patras, Greece, September 14–16, 2015, Proceedings |
Publisher | Springer Verlag |
Pages | 361-372 |
ISBN (Electronic) | 9783662483503 |
ISBN (Print) | 9783662483497 |
DOIs | |
Publication status | Published - Jul 2015 |
Event | European Symposium on Algorithms - , United Kingdom Duration: 14 Sept 2015 → … |
Publication series
Name | Lecture Notes in Computer Science |
---|---|
Publisher | Springer |
Volume | 9294 |
ISSN (Print) | 0302-9743 |
Conference
Conference | European Symposium on Algorithms |
---|---|
Country/Territory | United Kingdom |
Period | 14/09/15 → … |
Bibliographical note
The paper was initially rejected due to an oversight by the Program Committee. Two papers were submitted on the same topic but were not directly compared. After we enquired, the PC compared our paper to the other and decided that we both should have been accepted.Keywords
- cs.DS
Fingerprint
Dive into the research topics of 'Dictionary matching in a stream'. Together they form a unique fingerprint.Projects
- 1 Finished
-
Next generation pattern matching
Clifford, R. (Principal Investigator)
1/01/13 → 14/01/19
Project: Research
Profiles
-
Dr Raphael Clifford
- School of Computer Science - Reader in Algorithm Design
- Intelligent Systems Laboratory
- Algorithms and Complexity
Person: Academic , Member, Group lead