2015/04/23 by Raphaël Clifford, Allyx Fontaine, Clifford, Raphael +7 · 1 citation
Computer Science · #Algorithms and Data Compression #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Network Packet Processing and Optimization #semigroups and automata theory
paper · doi:10.48550/arxiv.1504.06242
openalex publication_date 2015/04/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.