Abstract

Repeated patterns and related phenomena in words are known to play a central role in many facets of computer science, telecommunications, coding, intrusion detection, twitter classification, data compression, data mining, and molecular biology. We will first review several pattern matching problems (i.e., exact string matching, constrained pattern matching, generalized pattern matching, and subsequence pattern matching). Then we discuss selected applications (i.e., digital trees, suffix trees, Lempel-Ziv'77 and Lempel-Ziv'78 data compression schemes, and finally the string complexity).

This talk is based on yet unpublished book, co-authored by P. Jacquet, with the same title as the talk.

Video Recording