CPM 2019

30th Annual Symposium on Combinatorial Pattern Matching

Pisa, Italy, June 18-20, 2019


Papers and Proceedings

Local information


Accepted papers

Nicola Prezza. Optimal Rank and Select Queries on Dictionary-Compressed Text
Haitao Jiang, Jiong Guo, Daming Zhu and Binhai Zhu. A 2-Approximation Algorithm for the Complementary Maximal Strip Recovery Problem
Eitan Kondratovsky and Amihood Amir. Sufficient Conditions for Efficient Indexing under Different Matchings
Nicola Prezza and Giovanna Rosone. Space-Efficient Computation of the LCP Array from the Burrows-Wheeler Transform
Niko Kiirala, Leena Salmela and Alexandru I. Tomescu. Safe and complete algorithms for dynamic programming problems, with an application to RNA folding
Takaaki Nishimoto and Yasuo Tabei. Conversion from RLBWT to LZ77
Djamal Belazzougui and Fabio Cunial. Fully-functional bidirectional Burrows-Wheeler indexes
Michał Gańczorz. Entropy lower bounds for dictionary compression
Raffaele Giancarlo, Giovanni Manzini, Giovanna Rosone and Marinella Sciortino. A New Class of Searchable and Provably Highly Compressible String Transformations
Dmitry Kosolobov and Nikita Sivukhin. Compressed Multiple Pattern Matching
Karim Labib, Przemysław Uznański and Daniel Wolleb-Graf. Hamming distance completeness
Jan Studený and Przemysław Uznański. Approximating Approximate Pattern Matching
Sung Gwan Park, Amihood Amir, Gad M. Landau and Kunsoo Park. Cartesian Tree Matching and Indexing
Hideo Bannai, Juha Kärkkäinen, Dominik Köppl and Marcin Piątkowski. Indexing the Bijective BWT
Julian Pape-Lange. On Maximal Repeats in Compressed Strings
Ali Akhavi, Julien Clément, Dimitri Darthenay, Loïck Lhote and Brigitte Vallee. Dichotomic selection on words: a probabilistic analysis
Hayam Alamro, Golnaz Badkobeh, Djamal Belazzougui, Costas S. Iliopoulos and Simon J. Puglisi. Computing the Antiperiod(s) of a String
Laurent Bulteau, Konrad K. Dabrowski, Guillaume Fertin, Matthew Johnson, Daniel Paulusma and Stephane Vialette. Finding a Small Number of Colourful Components
Pawel Gawrychowski and Tatiana Starikovskaya. Streaming dictionary matching with mismatches
Pawel Gawrychowski, Jakub Radoszewski and Tatiana Starikovskaya. Quasi-periodicity in streams
Ryo Sugahara, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai and Masayuki Takeda. Computing runs on a trie
Bastien Cazaux and Eric Rivals. Linking BWT and XBW via Aho-Corasick automaton: applications to Run-Length Encoding
Mai Alzamel, Maxime Crochemore, Costas Iliopoulos, Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter, Juliusz Straszyński, Tomasz Waleń and Wiktor Zuba. Quasi-Linear-Time Algorithm for Longest Common Circular Factor
Diego Diaz-Dominguez, Travis Gagie and Gonzalo Navarro. Simulating the DNA string graph in succinct space
Mitsuru Funakoshi, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai and Masayuki Takeda. Faster queries for longest substring palindrome after block edit
Giulia Bernardini, Paola Bonizzoni, Gianluca Della Vedova and Murray Patterson. A rearrangement distance for fully-labelled trees
Yuki Urabe, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai and Masayuki Takeda. On the Size of Overlapping Lempel-Ziv and Lyndon Factorizations
Diptarama Hendrian, Takuya Takagi and Shunsuke Inenaga. Online Algorithms for Constructing Linear-size Suffix Trie
Oleg Merkurev and Arseny Shur. Searching Long Repeats in Streams