Abstract
In the streaming multipattern search problem, which is also known as the streaming dictionary matching problem, a set D={P_1,P_2, . . . ,P_d} of d patterns (strings over an alphabet Sigma), called the dictionary, is given to be preprocessed. Then, a text T arrives one character at a time and the goal is to report, before the next character arrives, the longest pattern in the dictionary that is a current suffix of T. We prove that for a constant size alphabet, there exists a randomized MonteCarlo algorithm for the streaming dictionary matching problem that takes constant time per character and uses O(d log m) words of space, where m is the length of the longest pattern in the dictionary. In the case where the alphabet size is not constant, we introduce two new randomized MonteCarlo algorithms with the following complexities:
* O(log log Sigma) time per character in the worst case and O(d log m) words of space.
* O(1/epsilon) time per character in the worst case and O(d \Sigma^epsilon log m/epsilon) words of space for any 0<epsilon<= 1.
These results improve upon the algorithm of [Clifford et al., ESA'15] which uses O(d log m) words of space and takes O(log log (m+d)) time per character.
BibTeX  Entry
@InProceedings{golan_et_al:LIPIcs:2017:7855,
author = {Shay Golan and Ely Porat},
title = {{RealTime Streaming MultiPattern Search for Constant Alphabet}},
booktitle = {25th Annual European Symposium on Algorithms (ESA 2017)},
pages = {41:141:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770491},
ISSN = {18688969},
year = {2017},
volume = {87},
editor = {Kirk Pruhs and Christian Sohler},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7855},
URN = {urn:nbn:de:0030drops78550},
doi = {10.4230/LIPIcs.ESA.2017.41},
annote = {Keywords: multipattern, dictionary, streaming pattern matching, fingerprints}
}
Keywords: 

multipattern, dictionary, streaming pattern matching, fingerprints 
Collection: 

25th Annual European Symposium on Algorithms (ESA 2017) 
Issue Date: 

2017 
Date of publication: 

01.09.2017 