Name
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1007/978-3-662-48350-3_31 | ALGORITHMS - ESA 2015 |
Field | DocType | Volume |
Discrete mathematics,Computer science,Arithmetic,Theoretical computer science,Binary search algorithm,Pattern matching,Arithmetic progression | Journal | 9294 |
ISSN | Citations | PageRank |
0302-9743 | 9 | 0.53 |
References | Authors | |
13 | 5 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Raphaël Clifford | 1 | 268 | 28.57 |
| Allyx Fontaine | 2 | 9 | 0.53 |
| ely porat | 3 | 1007 | 79.16 |
| Benjamin Sach | 4 | 93 | 11.40 |
| Tatiana A. Starikovskaya | 5 | 9 | 0.53 |