Projects per year
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.
|Title of host publication||Algorithms – ESA 2015|
|Subtitle of host publication||23rd Annual European Symposium, Patras, Greece, September 14–16, 2015, Proceedings|
|Publication status||Published - Jul 2015|
|Event||European Symposium on Algorithms - , United Kingdom|
Duration: 14 Sep 2015 → …
|Name||Lecture Notes in Computer Science|
|Conference||European Symposium on Algorithms|
|Period||14/09/15 → …|
Bibliographical noteThe 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.