Skip to main content
  • Conference proceedings
  • © 2009

Combinatorial Pattern Matching

20th Annual Symposium, CPM 2009 Lille, France, June 22-24, 2009 Proceedings

Part of the book series: Lecture Notes in Computer Science (LNCS, volume 5577)

Part of the book sub series: Theoretical Computer Science and General Issues (LNTCS)

Conference series link(s): CPM: Annual Symposium on Combinatorial Pattern Matching

Conference proceedings info: CPM 2009.

Buy it now

Buying options

eBook USD 39.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book USD 54.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Other ways to access

This is a preview of subscription content, log in via an institution to check for access.

Table of contents (31 papers)

  1. Front Matter

  2. CPM’s 20th Anniversary: A Statistical Retrospective

    • Elena Yavorska Harris, Thierry Lecroq, Gregory Kucherov, Stefano Lonardi
    Pages 1-11
  3. Quasi-distinct Parsing and Optimal Compression Methods

    • Amihood Amir, Yonatan Aumann, Avivit Levy, Yuri Roshko
    Pages 12-25
  4. Generalized Substring Compression

    • Orgad Keller, Tsvi Kopelowitz, Shir Landau, Moshe Lewenstein
    Pages 26-38
  5. Contracted Suffix Trees: A Simple and Dynamic Text Indexing Data Structure

    • Andrzej Ehrenfeucht, Ross M. McConnell, Sung-Whan Woo
    Pages 41-53
  6. Linear Time Suffix Array Construction Using D-Critical Substrings

    • Ge Nong, Sen Zhang, Wai Hong Chan
    Pages 54-67
  7. Reoptimization of the Shortest Common Superstring Problem

    • Davide Bilò, Hans-Joachim Böckenhauer, Dennis Komm, Richard Královič, Tobias Mömke, Sebastian Seibert et al.
    Pages 78-91
  8. LCS Approximation via Embedding into Local Non-repetitive Strings

    • Gad M. Landau, Avivit Levy, Ilan Newman
    Pages 92-105
  9. Fast Searching in Packed Strings

    • Philip Bille
    Pages 116-126
  10. New Complexity Bounds for Image Matching under Rotation and Scaling

    • Christian Hundt, Maciej Liśkiewicz
    Pages 127-141
  11. Online Approximate Matching with Non-local Distances

    • Raphaël Clifford, Benjamin Sach
    Pages 142-153
  12. Approximate Matching for Run-Length Encoded Strings Is 3sum-Hard

    • Kuan-Yu Chen, Ping-Hui Hsu, Kun-Mao Chao
    Pages 168-179
  13. Permuted Longest-Common-Prefix Array

    • Juha Kärkkäinen, Giovanni Manzini, Simon J. Puglisi
    Pages 181-192
  14. Periodic String Comparison

    • Alexander Tiskin
    Pages 193-206
  15. Deconstructing Intractability: A Case Study for Interval Constrained Coloring

    • Christian Komusiewicz, Rolf Niedermeier, Johannes Uhlmann
    Pages 207-220

Other Volumes

  1. Combinatorial Pattern Matching

Editors and Affiliations

  • LIFL - Bâtiment M3 59655 Villeneuve d’Ascq Cédex,, France

    Gregory Kucherov

  • Department of Computer Science, University of Helsinki,, Finland

    Esko Ukkonen

Bibliographic Information

Buy it now

Buying options

eBook USD 39.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book USD 54.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Other ways to access