String matching algorithms are everywhere. You use them every day,
perhaps even without noticing. Whenever your mail client filters out
spam, whenever your spell checker flags a spelling mistake, whenever
your search engine of choice presents you with results it deems useful,
to list just some examples. For many applications, we need more than
finding exact occurrences of a pattern string in a text. Hence, in this
talk, I consider the classical problem of finding parts of a text that
are close to a given pattern string.
In particular, I consider the problem of finding all parts of a given
text that can be transformed to a given pattern string by inserting,
deleting, or substituting at most k characters—the Approximate String
Matching problem. The first algorithms for this problem were developed
in the 1970s, some of them are relevant even today. After a long line of
research, around the year 2000, the progress in obtaining faster
algorithms for Approximate String Matching came to a halt—even though
the interest did not fade.
In a recent series of papers, I and coauthors improved the more than
20-year-old state-of-the-art algorithms. In this talk, I highlight the
new tools and techniques that we developed for Approximate String
Matching. Further, I give an overview of additional applications of our
techniques to settings where text and pattern are given in a compressed
setting or where we allow text and pattern to change dynamically.