2026-07-23T16:05:13Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:7855 2024-03-06T10:41:20Z ddc:004 open_access

Real-Time Streaming Multi-Pattern Search for Constant Alphabet Golan, Shay Porat, Ely multi-pattern dictionary streaming pattern matching fingerprints In the streaming multi-pattern 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 Monte-Carlo 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 Monte-Carlo 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Shay Golan and Ely Porat 2017 Is Part Of LIPIcs, Volume 87, 25th Annual European Symposium on Algorithms (ESA 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2017.41 urn:nbn:de:0030-drops-78550 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2017.41 eng https://creativecommons.org/licenses/by/3.0/legalcode