Tatiana Starikovskaya,
équipe TAlgo, INRIA et
département informatique
de l’ENS Paris

The slides are here: hamming_compressed

Given a text and a pattern, computing all occurrences of the pattern in the text in one of the fundamental problems of stringology, which has myriads applications in practice (think of searching for a keyword in a long file).

However, in real life a pattern may never match the text exactly, and one should instead aim to find locations where it is only similar to the text.

In this course, we will consider one of the possible formulations of this task, which requires computing the Hamming distance (the number of mismatches) between a pattern of length m and every m-length substring of the text. We will discuss recent advances and open questions related to this famous problem.