CPM 2022

33rd Annual Symposium on Combinatorial Pattern Matching

Prague, Czech Republic, June 27–29, 2022


Update (26th June): Last-minute change to Sessions V and IX. Session V (starting Tuesday at 09:00) and Session IX (Wednesday, 11:55) are swapped.

    Skip to day:
  1. Monday
  2. Tuesday
  3. Wednesday
    Select timezone:
  1. Venue time
  2. My local time

Monday, June 27, 2022

08:00 - 08:50 Registration
08:50 - 09:00 Opening Remarks
Invited Talk I (Chair: Jan Holub)
09:00 - 10:00

Sharma V. Thankachan

Compact Text Indexing for Advanced Pattern Matching Problems: Parameterized, Order-isomorphic, 2D, etc.
10:00 - 10:20 Coffee break
Session I (Chair: Solon Pissis)
10:20 - 10:45

Yuma Arakawa, Gonzalo Navarro, and Kunihiko Sadakane

Bi-directional r-indexes
Paper icon
10:45 - 11:10

Nicola Rizzo, and Veli Mäkinen

Indexable Elastic Founder Graphs of Minimum Height
11:10 - 11:35

Takuya Mieno, Shunsuke Inenaga, and Takashi Horiyama

RePair Grammars are the Smallest Grammars for Fibonacci Words
11:35 - 11:55 Break
Session II (Chair: Golnaz Badkobeh)
11:55 - 12:20

Davide Cenzato, and Zsuzsanna Liptak

A theoretical and experimental analysis of BWT variants for string collections
12:20 - 12:45

Diego Diaz, and Gonzalo Navarro

Efficient Construction of the BWT for Repetitive Text Using String Compression
12:45 - 13:10

Avivit Levy, Ely Porat, and B. Riva Shalom

Partial Permutations Comparison, Maintenance and Applications
13:10 - 14:30 Lunch
Highlight Talk I (Chair: Esko Ukkonen)
14:30 - 15:00

Tomasz Kociumaka

Small space and streaming pattern matching with k edits
Session III (Chair: Jakub Radoszewski)
15:00 - 15:25

Tsubasa Oizumi, Takeshi Kai, Takuya Mieno, Shunsuke Inenaga, and Hiroki Arimura

Cartesian Tree Subsequence Matching
Paper icon
15:25 - 15:50

Philip Bille, Inge Li Gørtz, Shay Mozes, Teresa Anna Steiner, and Oren Weimann

The Fine-Grained Complexity of Episode Matching
15:50 - 16:10 Cofee break
Session IV (Chair: Shunsuke Inenaga)
16:10 - 16:35

Abhinav Nellore, and Rachel Ward

Arbitrary-length analogs to de Bruijn sequences
16:35 - 17:00

Giulia Bernardini, Huiping Chen, Grigorios Loukides, Solon Pissis, Leen Stougie, and Michelle Sweering

Making de Bruijn Graphs Eulerian
17:00 - 17:10 Break
17:10 - 17:40 Business Meeting

Back to top

Tuesday, June 28, 2022

Session V (Chair: Inge Li Gørtz)
09:00 - 09:25

Vincent Jugé

Reduction ratio of the IS-algorithm: worst and random cases
09:25 - 09:50

Tooru Akagi, Kouta Okabe, Takuya Mieno, Yuto Nakashima, and Shunsuke Inenaga

Minimal Absent Words on Run-Length Encoded Strings
Paper icon
09:50 - 10:15

Laurent Bulteau, Philippe Gambette, and Olga Seminck

Reordering a tree according to an order on its leaves
10:15 - 10:35 Coffee break
Session VI (Chair: Tomasz Kociumaka)
10:35 - 11:00

Giulia Bernardini, Alessio Conte, Esteban Gabory, Roberto Grossi, Grigorios Loukides, Solon Pissis, Giulia Punzi, and Michelle Sweering

On Strings Having the Same Length-k Substrings
11:00 - 11:25

Panagiotis Charalampopoulos, Solon Pissis, and Jakub Radoszewski

Longest Palindromic Substring in Sublinear Time
11:25 - 11:50

Davaajav Jargalsaikhan, Diptarama Hendrian, Ryo Yoshinaka, and Ayumi Shinohara

Parallel algorithm for pattern matching problems under substring consistent equivalence relations
11:50 - 12:10 Break
Invited Talk II (Chair: Gad Landau)
12:10 - 13:10

Jeffrey Shallit

Using automata and a decision procedure to prove results in pattern matching
13:10 - 14:30 Lunch
Highlight Talk II (Chair: Nadia Pisanti)
14:30 - 15:00

Moses Ganardi

Compression by Contracting Straight-Line Programs
Session VII (Chair: Maxime Crochemore)
15:00 - 15:25

Raphael Clifford, Pawel Gawrychowski, Tomasz Kociumaka, Daniel Martin, and Przemysław Uznański

The Dynamic k-Mismatch Problem

(Recipient of the Best Paper Award)

15:25 - 15:50

Dana Fisman, Joshua Grogin, Oded Margalit, and Gera Weiss

The Normalized Edit Distance with Uniform Operation Costs is a Metric
15:50 Excursion and Conference Dinner

Back to top

Wednesday, June 29, 2022

Invited Talk III (Chair: Hideo Bannai)
09:00 - 10:00

Takehiro Ito

Invitation to Combinatorial Reconfiguration
Paper icon
10:00 - 10:20 Coffee break
Session VIII (Chair: Gabriele Fici)
10:20 - 10:45

Maxime Crochemore, Costas Iliopoulos, Jakub Radoszewski, Wojciech Rytter, Juliusz Straszyński, Tomasz Walen, and Wiktor Zuba

Linear-Time Computation of Shortest Covers of All Rotations of a String
10:45 - 11:10

Jakub Radoszewski, Wojciech Rytter, Juliusz Straszyński, Tomasz Walen, and Wiktor Zuba

Rectangular Tile Covers of 2D-strings
11:10 - 11:35

Laurent Bulteau, Guillaume Fertin, Vincent Jugé, and Stéphane Vialette

Permutation Pattern Matching for Doubly Partially Ordered Patterns
11:35 - 11:55 Break
Session IX (Chair: Pawel Gawrychowski)
11:55 - 12:20

Laurent Bulteau, Mark Jones, Rolf Niedermeier, and Till Tantau

An FPT-Algorithm for Longest Common Subsequence Parameterized by the Maximum Number of Deletions
12:20 - 12:45

Wenfeng Lai, Adiesha Liyanage, Binhai Zhu, and Peng Zou

Beyond the Longest Letter-duplicated Subsequence Problem
Paper icon
12:45 - 13:10

Yuichi Asahiro, Jesper Jansson, Guohui Lin, Eiji Miyano, Hirotaka Ono, and Tadatoshi Utashima

Polynomial-Time Equivalence and Refined Algorithms for Longest Common Subsequence Variants
13:10 - 14:30 Lunch
Session X (Chair: Zsuzsanna Liptak)
14:30 - 14:55

Golnaz Badkobeh, Maxime Crochemore, Jonas Ellert, and Cyril Nicaud

Back-to-Front Online Lyndon Forest Construction
14:55 - 15:20

John Machacek

Mechanical proving with Walnut for squares and cubes in partial words
Paper icon
15:20 - 15:25 Closing Remarks

Back to top