CPM 2021

32nd Annual Symposium on Combinatorial Pattern Matching

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


Papers and proceedings

Local information




Display timezone:

Monday 5th | Tuesday 6th | Wednesday 7th

Sunday, July 4, 2021

Summer School I (chair: Artur Jeż)
Jakub Radoszewski
Quasiperiodicity in Strings
Summer School II (chair: Przemysław Uznański)
Martin Farach-Colton
Balls, Bins, Hashes, Filters, Stashes, Positive Queries, Negative Queries. And Succinctness

Monday, July 5, 2021

Opening remarks
Session I (chair: Marinella Sciortino)
Takaaki Nishimoto and Yasuo Tabei
R-enum: Enumeration of Characteristic Substrings in BWT-runs Bounded Space
Hideo Bannai, Juha Kärkkäinen, Dominik Köppl and Marcin Piątkowski
Constructing the Bijective BWT
Sung-Hwan Kim and Hwan-Gue Cho
A Compact Index for Cartesian Tree Matching
Golnaz Badkobeh, Panagiotis Charalampopoulos and Solon Pissis
Internal Shortest Absent Word Queries
Invited Talk (chair: Philip Bille)
Nadia Pisanti
On-line Algorithms and Applications for Pattern Matching on Degenerate Texts
Highlight Talk (chair: Paweł Gawrychowski)
Travis Gagie
Working in BWT-Runs Bounded Space
Session II (chair: Oren Weimann)
Djamal Belazzougui, Dmitry Kosolobov, Simon Puglisi and Rajeev Raman
Weighted Ancestors in Suffix Trees Revisited
Meng He and Serikzhan Kazi
Data Structures for Categorical Path Counting Queries
Dustin Cobas, Travis Gagie and Gonzalo Navarro
A Fast and Small Subsampled R-index
Business meeting

Tuesday, July 6, 2021

Session III (chair: Gregory Kucherov)
Sangsoo Park, Sung Gwan Park, Bastien Cazaux, Kunsoo Park and Eric Rivals
A Linear Time Algorithm for Constructing Hierarchical Overlap Graphs
Shahbaz Khan
Optimal Construction of Hierarchical Overlap Graphs
Panagiotis Charalampopoulos, Jakub Radoszewski, Wojciech Rytter, Tomasz Walen and Wiktor Zuba
Computing Covers of 2D-Strings
Giuseppe F. Italiano, Nicola Prezza, Blerina Sinaimeri and Rossano Venturini
Compressed Weighted de Bruijn Graphs
Invited Talk (chair: Gad Landau)
Michal Koucký
Computing edit distance
Session IV (chair: Zsuzsanna Lipták)
Duncan Adamson, Argyrios Deligkas, Vladimir Gusev and Igor Potapov
Ranking Bracelets in Polynomial Time
Keegan Yao and Mukul S. Bansal
Optimal Completion and Comparison of Incomplete Phylogenetic Trees Under Robinson-Foulds Distance
Laurent Bulteau, Samuele Giraudo and Stéphane Vialette
Disorders and permutations
Andrei Popa and Alexandru Popa
Efficient algorithms for counting gapped palindromes
Walking tour of the center

Wednesday, July 7, 2021

Session V (chair: Tomasz Waleń)
Takuya Mieno, Solon Pissis, Michelle Sweering and Leen Stougie
String Sanitization Under Edit Distance: Improved and Generalized
Philip Bille, Inge Li Gørtz, Max Pedersen and Teresa Anna Steiner
Gapped Indexing for Consecutive Occurrences
Amihood Amir, Itai Boneh and Eitan Kondratovsky
The k-mappability problem revisited
Giulia Bernardini, Alberto Marchetti-Spaccamela, Solon Pissis, Leen Stougie and Michelle Sweering
Constructing Strings Avoiding Forbidden Substrings
Invited Talk (chair: Inge Li Gørtz)
Hideo Bannai
Repetitions in strings: a "constant" problem
Highlight Talk (chair: Tatiana Starikovskaya)
Panagiotis Charalampopoulos
Faster Approximate Pattern Matching: A Unified Approach
Session VI (chair: Solon Pissis)
Joshua Sobel, Noah Bertram, Chen Ding, Fatemeh Nargesian and Daniel Gildea
AWLCO: All-Window Length Co-Occurrence
Riccardo Dondi and Florian Sikora
The Longest Run Subsequence Problem: Further Complexity Results
Abhinav Nellore, Austin Nguyen and Reid Thompson
An invertible transform for efficient string matching in labeled digraphs
Closing Remarks