CPM 2021

32nd Annual Symposium on Combinatorial Pattern Matching

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

Conference

Papers and proceedings

Local information

Travel

Other

Programme

Display timezone:

Monday 5th | Tuesday 6th | Wednesday 7th

Sunday, July 4, 2021

Summer School I (chair: Artur Jeż)
Jakub Radoszewski
Quasiperiodicity in Strings
 
Lunch
 
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
 
Break
 
Invited Talk (chair: Philip Bille)
Nadia Pisanti
On-line Algorithms and Applications for Pattern Matching on Degenerate Texts
 
Lunch
 
Highlight Talk (chair: Paweł Gawrychowski)
Travis Gagie
Working in BWT-Runs Bounded Space
 
Break
 
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
 
Break
 
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
 
Break
 
Invited Talk (chair: Gad Landau)
Michal Koucký
Computing edit distance
 
Lunch
 
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
 
Break
 
Invited Talk (chair: Inge Li Gørtz)
Hideo Bannai
Repetitions in strings: a "constant" problem
 
Lunch
 
Highlight Talk (chair: Tatiana Starikovskaya)
Panagiotis Charalampopoulos
Faster Approximate Pattern Matching: A Unified Approach
 
Break
 
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