This book constitutes the refereed proceedings of the 12th Annual Symposium on Combinatorial Pattern Matching, CPM 2001, held in Jerusalem, Israel, in July 2001.
The 21 revised papers presented together with one invited paper were carefully reviewed and selected from 35 submissions. The papers are devoted to current theoretical and algorithmic issues of searching and matching strings and more complicated patterns such as trees, regular expressions, graphs, point sets, and arrays as well as to advanced applications of CPM in areas such as the Internet, computational biology, multimedia systems, information retrieval, data compression, coding, computer vision, and pattern recognition.
Author(s): Gad M. Landau (auth.), Amihood Amir (eds.)
Series: Lecture Notes in Computer Science 2089
Edition: 1
Publisher: Springer-Verlag Berlin Heidelberg
Year: 2001
Language: English
Pages: 280
Tags: Algorithm Analysis and Problem Complexity; Pattern Recognition; Information Storage and Retrieval; Coding and Information Theory; Combinatorics
Regular Expression Searching over Ziv-Lempel Compressed Text....Pages 1-17
Parallel Lempel Ziv Coding (Extended Abstract)....Pages 18-30
Approximate Matching of Run-Length Compressed Strings....Pages 31-49
What to Do with All this Hardware? (Invited Lecture)....Pages 50-50
Efficient Experimental String Matching by Weak Factor Recognition * ....Pages 51-72
Better Filtering with Gapped q-Grams....Pages 73-85
Fuzzy Hamming Distance: A New Dissimilarity Measure (Extended Abstract)....Pages 86-97
An Extension of the Periodicity Lemma to Longer Periods (Invited Lecture)....Pages 98-105
A Very Elementary Presentation of the Hannenhalli-Pevzner Theory....Pages 106-117
Tandem Cyclic Alignment....Pages 118-130
An Output-Sensitive Flexible Pattern Discovery Algorithm....Pages 131-142
Episode Matching * ....Pages 143-146
String Resemblance Systems: A Unifying Framework for String Similarity with Applications to Literature and Music....Pages 147-151
Efficient Discovery of Proximity Patterns with Suffix Arrays (Extended Abstract)....Pages 152-156
Computing the Equation Automaton of a Regular Expression in O(s 2 ) Space and Time....Pages 157-168
On-Line Construction of Compact Directed Acyclic Word Graphs * ....Pages 169-180
Linear-Time Longest-Common-Prefix Computation in Suffix Arrays and Its Applications....Pages 181-192
Multiple Pattern Matching Algorithms on Collage System....Pages 193-206
Finding All Common Intervals of k Permutations....Pages 207-218
Generalized Pattern Matching and the Complexity of Unavoidability Testing....Pages 219-230
Balanced Suffix Trees (Invited Lecture)....Pages 231-231
A Fast Algorithm for Optimal Alignment between Similar Ordered Trees....Pages 232-240
Minimum Quartet Inconsistency Is Fixed Parameter Tractable....Pages 241-256
Optimally Compact Finite Sphere Packings — Hydrophobic Cores in the FCC....Pages 257-271
