CPM 2022

33rd Annual Symposium on Combinatorial Pattern Matching

Prague, Czech Republic, June 27–29, 2022

Accepted papers

These papers were accepted to CPM 2022 conference:

  • Davide Cenzato and Zsuzsanna Liptak: A theoretical and experimental analysis of BWT variants for string collections
  • Laurent Bulteau, Mark Jones, Rolf Niedermeier and Till Tantau: An FPT-Algorithm for Longest Common Subsequence Parameterized by the Maximum Number of Deletions
  • Abhinav Nellore and Rachel Ward: Arbitrary-length analogs to de Bruijn sequences
  • Golnaz Badkobeh, Maxime Crochemore, Jonas Ellert and Cyril Nicaud: Back-to-Front Online Lyndon Forest Construction
  • Wenfeng Lai, Adiesha Liyanage, Binhai Zhu and Peng Zou: Beyond the Longest Letter-duplicated Subsequence Problem
  • Yuma Arakawa, Gonzalo Navarro and Kunihiko Sadakane: Bi-directional r-indexes
  • Tsubasa Oizumi, Takeshi Kai, Takuya Mieno, Shunsuke Inenaga and Hiroki Arimura: Cartesian Tree Subsequence Matching
  • Diego Diaz and Gonzalo Navarro: Efficient Construction of the BWT for Repetitive Text Using String Compression
  • Nicola Rizzo and Veli Mäkinen: Indexable Elastic Founder Graphs of Minimum Height
  • 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
  • Panagiotis Charalampopoulos, Solon Pissis and Jakub Radoszewski: Longest Palindromic Substring in Sublinear Time
  • Giulia Bernardini, Huiping Chen, Grigorios Loukides, Solon Pissis, Leen Stougie and Michelle Sweering: Making de Bruijn Graphs Eulerian
  • John Machacek: Mechanical proving with Walnut for squares and cubes in partial words
  • Tooru Akagi, Kouta Okabe, Takuya Mieno, Yuto Nakashima and Shunsuke Inenaga: Minimal Absent Words on Run-Length Encoded Strings
  • 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
  • Davaajav Jargalsaikhan, Diptarama Hendrian, Ryo Yoshinaka and Ayumi Shinohara: Parallel algorithm for pattern matching problems under substring consistent equivalence relations
  • Avivit Levy, Ely Porat and B. Riva Shalom: Partial Permutations Comparison, Maintenance and Applications
  • Laurent Bulteau, Guillaume Fertin, Vincent Jugé and Stéphane Vialette: Permutation Pattern Matching for Doubly Partially Ordered Patterns
  • Yuichi Asahiro, Jesper Jansson, Guohui Lin, Eiji Miyano, Hirotaka Ono and Tadatoshi Utashima: Polynomial-Time Equivalence and Refined Algorithms for Longest Common Subsequence Variants
  • Jakub Radoszewski, Wojciech Rytter, Juliusz Straszyński, Tomasz Walen and Wiktor Zuba: Rectangular Tile Covers of 2D-strings
  • Vincent Jugé: Reduction ratio of the IS-algorithm: worst and random cases
  • Laurent Bulteau, Philippe Gambette and Olga Seminck: Reordering a tree according to an order on its leaves
  • Takuya Mieno, Shunsuke Inenaga and Takashi Horiyama: RePair Grammars are the Smallest Grammars for Fibonacci Words
  • Raphael Clifford, Pawel Gawrychowski, Tomasz Kociumaka, Daniel Martin and Przemysław Uznański: The Dynamic k-Mismatch Problem
  • Philip Bille, Inge Li Gørtz, Shay Mozes, Teresa Anna Steiner and Oren Weimann: The Fine-Grained Complexity of Episode Matching
  • Dana Fisman, Joshua Grogin, Oded Margalit and Gera Weiss: The Normalized Edit Distance with Uniform Operation Costs is a Metric