CPM 2021

32nd Annual Symposium on Combinatorial Pattern Matching

Wrocław, Poland, July 5–7, 2021

Conference

Papers and proceedings

Local information

Travel

Other

Summer school

There will be a full-day summer school on July 4.

Jakub Radoszewski (University of Warsaw)

Title: Quasiperiodicity in Strings

An elementary notion that grasps repetitiveness in strings is periodicity. If a string can be generated by repeated concatenation of its smaller piece, then we say that it is periodic. The field of periodicity was generalized by allowing not only concatenation, but also superpositions, which resulted in the introduction of quasiperiodicity. The basic notions of quasiperiodicity are covers and seeds. A cover of a text T is a string whose occurrences in T cover all positions of T, while a seed of T is a cover of some superstring of T.

During the lecture I will present important properties of covers and seeds and show algorithms for computing them, survey other notions of quasiperiodicity (including approximate quasiperiodicity) and known results, and list open problems in this area. The course will also include a tutorial session with exercises on quasiperiodicity.

Martin Farach-Colton (Rutgers University)

Title: Balls, Bins, Hashes, Filters, Stashes, Positive Queries, Negative Queries. And Succinctness

Hashing is one of the most basic data structures. Everyone learns about chaining and a bit about open addressing. Topics such as space-efficient hash tables or constant-time operations are considered advanced. But recent innovations in hash tables has dramatically simplified such “advanced” guarantees. In this tutorial, we will cover recent results in hashing and their implications to such topics as filters. We will cover not only the theoretically best hash tables and filters but the fastest ones in practice. (Spoiler alert: they’re the same ones.)