Dictionary matching in a stream

Raphael Clifford, Allyx Fontaine, Ely Porat, Benjamin Sach, Tatiana Starikovskaya

Research output: Chapter in Book/Report/Conference proceedingConference Contribution (Conference Proceeding)

31 Citations (Scopus)
326 Downloads (Pure)


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 languageEnglish
Title of host publicationAlgorithms – ESA 2015
Subtitle of host publication23rd Annual European Symposium, Patras, Greece, September 14–16, 2015, Proceedings
PublisherSpringer Verlag
ISBN (Electronic)9783662483503
ISBN (Print)9783662483497
Publication statusPublished - Jul 2015
EventEuropean Symposium on Algorithms - , United Kingdom
Duration: 14 Sept 2015 → …

Publication series

NameLecture Notes in Computer Science
ISSN (Print)0302-9743


ConferenceEuropean Symposium on Algorithms
Country/TerritoryUnited Kingdom
Period14/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.


  • cs.DS


Dive into the research topics of 'Dictionary matching in a stream'. Together they form a unique fingerprint.

Cite this