7 citations · 26 across the 14 of their papers we have counts for
3 papers · 1 filter
The k-mismatch problem revisited
Raphaël Clifford, Allyx Fontaine, Ely Porat +2
We revisit the complexity of one of the most basic problems in pattern matching. In the k-mismatch problem we must compute the Hamming distance between a pattern of length m and ev…
Dictionary matching in a stream
Raphael Clifford, Allyx Fontaine, Ely Porat +2
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…
The complexity of computation in bit streams
Raphael Clifford, Markus Jalsenius, Benjamin Sach
We revisit the complexity of online computation in the cell probe model. We consider a class of problems where we are first given a fixed pattern or vector of symbols and t…