Speaker: Benjamin Sach (Bristol)
Title: New algorithms for pattern matching in streaming texts
Abstract: We will present some recent work on pattern matching in streaming texts. In this setting, a stream of text characters arrives one at a time and, in the most basic problem, the task is to report each occurrence of a given pattern string in the stream, as it occurs. We will begin by briefly discussing an existing algorithm for this problem which uses only logarithmic space in the pattern length.
The main focus will be on two natural generalisations of the basic problem. In the first generalisation, the single pattern string is replaced with a dictionary containing many pattern strings. In the second generalisation, a small number of mismatches (single character substitutions) are permitted. We will discuss new algorithms for both generalisations which use sub-linear (poly-logarithmic) space in the (longest) pattern length while matching (up to log factors) the time complexity of the fastest known offline algorithm for the corresponding generalisation.