Combinatorial Pattern Matching（组合模式匹配）

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.

Sharper Upper and Lower Bounds for an Approximation Scheme for CONSENSUS-PATTERN
On the Longest Common Rigid Subsequence Problem
Text Indexing with Errors
A New Compressed Suffix Tree Supporting Fast Search and Its Construction Algorithm Using Optimal Working Space
Succinct Suffix Arrays Based on Run-Length Encoding
Linear-Time Construction of Compressed Suffix Arrays Using o(n log n)-Bit Working Space for Large Alphabets
Farster Algorithms for 5,7-Matching and Related Problems
A Fast Algorithm for Approximate String Matching on Gene Sequences
Approximate Matching in the L1 Metric
An Efficient Algorithm for Generating Super Condensed Neighborhoods
The Median Problem for the Reversal Distance in Circular Bacterial Genomes
Using PQ Trees for Comparative Genomics
Hardness of Optimal Spaced Seed Design
Weighted Directed Word Graph
Construction of Aho Corasick Automaton in Linear Time for Integer Alphabets
An Extension of the Burrows Wheeler Transform and Applications to Sequence Comparison and Data Compression
DNA Compression Challenge Revisited:A Dynamic Programming Approach
On the Complexity of Sparse Exon Assembly
An Upper Bound on the Hardness of Exact Matrix Based Motif Discovery
Incremental Inference of Relational Motifs with a Degenerate Alphabet
Speeding up Parsing of Biological Context-Free Grammars
A New Periodicity Lemma
Two Dimensional Parameterized Matching
An Optimal Algorithm for Online Square Detection
A Simple Fast Hybrid Pattern-Matching Algorithm
Prefix-Free Regular-Expression Matching
Reducing the Size of NFAs by Using Equivalences and Preorders
Regular Expression Constrained Sequence Alignment
……
Author Index