Sequences of events, items, or tokens occurring in an ordered metric space appear often in
data and the requirement to detect and analyze frequent subsequences is a common …

The book is intended for lectures on string processes and pattern matching in Master's
courses of computer science and software engineering curricula. The details of algorithms …

The edit distance between two strings S and R is defined to be the minimum number of
character inserts, deletes, and changes needed to convert R to S. Given a text string t of …

This paper considers various flavors of the following online problem: preprocess a text or
collection of strings, so that given a query string p, all matches of p with the text can be …

In low-depth circuit complexity, the polynomial method is a way to prove lower bounds by
translating weak circuits into low-degree polynomials, then analyzing properties of these …

We describe some of the design choices that were made during the development of a fast,
scalable, inline, deduplication device. The system's design goals and how they were …

Grammar-based compression, where one replaces a long string by a small context-free
grammar that generates the string, is a simple and powerful paradigm that captures …

In the approximate pattern matching problem, given a text T, a pattern P, and a threshold k,
the task is to find (the starting positions of) all substrings of T that are at distance at most k …

We study the classic Text-to-Pattern Hamming Distances problem: given a pattern P of
length m and a text T of length n, both over a polynomial-size alphabet, compute the …

We propose a dedicated protocol for the highly motivated problem of secure two-party
pattern matching: Alice holds a text t∈{0, 1}*. of length n, while Bob has a pattern p∈{0, 1} …