This book constitutes the refereed proceedings of the 21st Annual Symposium on Combinatorial Pattern Matching, CPM 2010, held in New York, USA, in June 2010. The 28 revised full papers presented together with 3 invited talks were carefully reviewed and selected from 53 submissions. The papers address all areas related to combinatorial pattern matching and its applications, such as searching and matching strings and more complicated patterns such as trees, regular expressions, graphs, point sets, and arrays with special focus on coding and data compression, computational biology, data mining, information retrieval, natural language processing, pattern recognition, string algorithms, string processing in databases, symbolic computing and text searching.
The papers contained in this volume were presented at the 21st Annual S- posium on Combinatorial Pattern Matching (CPM 2010) held at NYU-Poly, Brooklyn, New York during June 21-23, 2010. Allthe paperspresentedatthe conferenceareoriginalresearchcontributions. We received 53 submissions from 21 countries. Each paper was reviewed by at least three reviewers. The committee decided to accept 28 papers. The program also includes three invited talks by Zvi Galil from Tel Aviv University, Israel, Richard M. Karp from University of California at Berkeley, USA, and Je?rey S. Vitter from Texas A&M University, USA. The objective of the annual CPM meetings is to provide an international forum for research in combinatorial pattern matching and related applications. It addresses issues of searching and matching strings and more complicated p- terns such as trees, regular expressions, graphs, point sets, and arrays. The goal is to derive non-trivialcombinatorialproperties of suchstructures and to exploit these properties in order to either achieve superior performance for the cor- sponding computational problems or pinpoint conditions under which searches cannot be performed e?ciently.
The meeting also deals with problems in c- putational biology, data compression and data mining, coding, information - trieval, natural language processing and pattern recognition. TheAnnual SymposiumonCombinatorialPatternMatchingstartedin 1990, andhassincetakenplaceeveryyear.PreviousCPM meetingswereheld inParis, London, Tucson, Padova, Asilomar, Helsinki, Laguna Beach, Aarhus, Pisc- away, Warwick, Montreal, Jerusalem, Fukuoka, Morelia, Istanbul, Jeju Island, Barcelona, London, Ontario, Pisa, and Lille.