Combinatorial Pattern Matching

1. Front Matter

   PDF

2. Forty Years of Text Indexing

   • Alberto Apostolico, Maxime Crochemore, Martin Farach-Colton, Zvi Galil, S. Muthukrishnan

   Pages 1-10

3. LCP Magic

   • Moshe Lewenstein

   Pages 11-11

4. Discrete Methods for Image Analysis Applied to Molecular Biology

   • Gene Myers

   Pages 12-12

5. Locating All Maximal Approximate Runs in a String

   • Mika Amit, Maxime Crochemore, Gad M. Landau

   Pages 13-27

6. On Minimal and Maximal Suffixes of a Substring

   • Maxim Babenko, Ignat Kolesnichenko, Tatiana Starikovskaya

   Pages 28-37

7. Converting SLP to LZ78 in almost Linear Time

   • Hideo Bannai, Paweł Gawrychowski, Shunsuke Inenaga, Masayuki Takeda

   Pages 38-49

8. A Bit-Parallel, General Integer-Scoring Sequence Alignment Algorithm

   • Gary Benson, Yozen Hernandez, Joshua Loving

   Pages 50-61

9. Compact q-Gram Profiling of Compressed Strings

   • Philip Bille, Patrick Hagge Cording, Inge Li Gørtz

   Pages 62-73

10. A Constant-Space Comparison-Based Algorithm for Computing the Burrows–Wheeler Transform

    • Maxime Crochemore, Roberto Grossi, Juha Kärkkäinen, Gad M. Landau

    Pages 74-82

11. Pattern Matching with Variables: A Multivariate Complexity Analysis

    • Henning Fernau, Markus L. Schmid

    Pages 83-94

12. New Algorithms for Position Heaps

    • Travis Gagie, Wing-Kai Hon, Tsung-Han Ku

    Pages 95-106

13. Document Listing on Repetitive Collections

    • Travis Gagie, Kalle Karhu, Gonzalo Navarro, Simon J. Puglisi, Jouni Sirén

    Pages 107-119

14. Approximating Shortest Superstring Problem Using de Bruijn Graphs

    • Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin

    Pages 120-129

15. Local Search for String Problems: Brute Force Is Essentially Optimal

    • Jiong Guo, Danny Hermelin, Christian Komusiewicz

    Pages 130-141

16. Space-Efficient Construction Algorithm for the Circular Suffix Tree

    • Wing-Kai Hon, Tsung-Han Ku, Rahul Shah, Sharma V. Thankachan

    Pages 142-152

17. Efficient Lyndon Factorization of Grammar Compressed Text

    • Tomohiro I, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda

    Pages 153-164

18. Approximation of Grammar-Based Compression via Recompression

    • Artur Jeż

    Pages 165-176

19. Fast Algorithm for Partial Covers in Words

    • Tomasz Kociumaka, Solon P. Pissis, Jakub Radoszewski, Wojciech Rytter, Tomasz Waleń

    Pages 177-188

20. Linear Time Lempel-Ziv Factorization: Simple, Fast, Small

    • Juha Kärkkäinen, Dominik Kempa, Simon J. Puglisi

    Pages 189-200

This book constitutes the refereed proceedings of the 24th Annual Symposium on Combinatorial Pattern Matching, CPM 2013, held in Bad Herrenalb (near Karlsruhe), Germany, in June 2013. The 21 revised full papers presented together with 2 invited talks were carefully reviewed and selected from 51 submissions. The papers address issues of searching and matching strings and more complicated patterns such as trees, regular expressions, graphs, point sets, and arrays. The goal is to derive non-trivial combinatorial properties of such structures and to exploit these properties in order to either achieve superior performance for the corresponding computational problem or pinpoint conditions under which searches cannot be performed efficiently. The meeting also deals with problems in computational biology, data compression and data mining, coding, information retrieval, natural language processing, and pattern recognition.

• NP-Completeness
• bit-parallelism
• external memory algorithms
• grammar-based compression
• text indexes
• algorithm analysis and problem complexity
• data structures

• Fakultät für Informatik, Institut für Theoretische Informatik, Karlsruhe Institut für Technology, Karlsruhe, Germany

  Johannes Fischer

• Karlsruhe Institute of Technology, Germany

  Peter Sanders

Policies and ethics