CPM 2014

25th Annual Symposium on Combinatorial Pattern Matching

Moscow, Russia, June 16-18, 2014



Local information





June 16 (Mon)

June 17 (Tue)

June 18 (Wed)


Special session:

25th anniversary of CPM

Invited talk by

Udi Manber

CPM 2015


Contributed talks


Contributed talks




Contributed talks

Excursion and dinner

Contributed talks





CPM 2014 Programme

June 16

08:30-09:00 Registration

09:00-10:00 Special Session of the 25th Anniversary of CPM

Alberto Apostolico. Sequence Comparison in the Time of Deluge.

10:00-10:20 Coffee break

10:20-11:20 Special Session of the 25th Anniversary of CPM

Maxime Crochemore. Repeats in Strings.

11:20-11:40 Coffee break

11:40-12:40 Special Session of the 25th Anniversary of CPM

Gene Myers. What's behind BLAST.

12:40-14:30 Lunch

14:30-16:10 Contributed talks

Amihood Amir and Benny Porat. Approximate On-line Palindrome Recognition, and Applications.

Roman Kolpakov, Mikhail Podolskiy, Mikhail Posypkin and Nickolay Khrapov. Searching of Gapped Repeats and Subrepetitions in a Word.

Tomasz Kociumaka, Solon Pissis, Jakub Radoszewski, Wojciech Rytter and Tomasz Walen. Efficient Algorithms for Shortest Partial Seeds in Words.

Tomohiro I, Shiho Sugimoto, Shunsuke Inenaga, Hideo Bannai and Masayuki Takeda. Computing Palindromic Factorizations and Palindromic Covers On-line.

16:10-16:30 Coffee break

16:30-18:10 Contributed talks

Gonzalo Navarro and Sharma V. Thankachan. Encodings for Range Majority Queries.

Philip Bille, Patrick Hagge Cording and Inge Li Gørtz. Compressed Subsequence Matching and Packed Tree Coloring.

Rashid Ibragimov, Jiong Guo and Jan Baumbach. Compactness-Preserving Mapping on Trees.

Stephane Durocher, Robert Fraser, Travis Gagie, Debajyoti Mondal, Matthew Skala and Sharma Thankachan. Indexed Geometric Jumbled Pattern Matching.

June 17

9:00-10:00 Invited talk

Udi Manber. How To Think Big.

10:00-10:20 Coffee break

10:20-11:35 Contributed talks

Ayelet Butman, Noa Lewenstein and Ian Munro. Permuted Scaled Matching.

Gregory Kucherov, Kamil Salikhov and Dekel Tsur. Approximate String Matching using a Bidirectional Index.

Kasper Green Larsen, Jesper Sindahl Nielsen, Sharma V. Thankachan and Ian Munro. On Hardness of Several String Indexing Problems.

11:35-11:50 Coffee break

11:50-12:40 Contributed talks

N. Jesper Larsson. Most Recent Match Queries in On-Line Suffix Trees.

Pawel Gawrychowski and Przemyslaw Uznanski. Order-preserving Pattern Matching with k Mismatches.

12:40-14:30 Lunch

14:30-18:30 Excursion

18:30-21:00 Dinner

June 18

09:00-09:25 CPM 2015

09:25-10:40 Contributed talks

Amihood Amir, Jessica Ficler, Liam Roditty and Oren Sar Shalom. On the Efficiency of the Hamming C-Centerstring Problems.

Danny Hermelin and Liat Rozenberg. Parameterized Complexity Analysis for the Closest String with Wildcards Problem.

Zhi-Zhong Chen, Bin Ma and Lusheng Wang. Randomized and Parameterized Algorithms for the Closest String Problem.

10:40-11:00 Coffee break

11:00-12:40 Contributed talks

Amir Carmel, Noa Musa-Lempel, Dekel Tsur and Michal Ziv-Ukelson. The Worst Case Complexity of Maximum Parsimony.

Bastien Cazaux, Thierry Lecroq and Eric Rivals. From Indexing Data Structures to de Bruijn Graphs.

Mingfu Shao and Bernard Moret. On the DCJ Median Problem.

Laurent Bulteau, Guillaume Fertin and Christian Komusiewicz. Reversal Distances for Strings with Few Blocks or Small Alphabets.

12:40-14:30 Lunch

14:30-16:10 Contributed talks

Amihood Amir, Avivit Levy, Ely Porat and Riva Shalom. Dictionary Matching with One Gap.

Guy Feigenblat, Ely Porat and Ariel Shiftan. An Improved Query Time for Succinct Dynamic Dictionary Matching.

Juha Kärkkäinen, Dominik Kempa and Simon Puglisi. String Range Matching.

Maxim Babenko, Pawel Gawrychowski, Tomasz Kociumaka and Tatiana Starikovskaya. Computing Minimal and Maximal Suffixes of a Substring Revisited.

16:10-16:30 Coffee break

16:30-18:10 Contributed talks

Atalay Mert Ileri, M. Oguzhan Kulekci and Bojian Xu. Shortest Unique Substring Query Revisited.

Artur Jez. A Really Simple Approximation of Smallest Grammar.

Péter Burcsi, Gabriele Fici, Zsuzsanna Liptak, Frank Ruskey and Joe Sawada. On Combinatorial Generation of Prefix Normal Words.

Tomasz Kociumaka, Jakub Radoszewski and Wojciech Rytter. Computing k-th Lyndon Word and Decoding Lexicographically Minimal de Bruijn Sequence.

18:10 Closing