Pattern Matching Algorithms [Hardcover]

Issues of matching and searching on elementary discrete structures arise pervasively in computer science and many of its applications, and their relevance is expected to grow as information is amassed and shared at an accelerating pace. Several algorithms were discovered as a result of these needs, which in turn created the subfield of Pattern Matching. This book provides an overview of the current state of Pattern Matching as seen by specialists who have devoted years of study to the field. It covers most of the basic principles and presents material advanced enough to faithfully portray the current frontier of research. Because of these recent advances, this is the right time for a book that brings together information relevant to both graduate students and specialists in need of an in-depth reference.

1. Off-Line Serial Exact String Searching,M. Crochemore
2. Off-Line Parallel Exact String Searching,Z. Galil and I. Yudkiewicz
3. On-Line String Searching,A. Apostolico
4. Serial Computations of Levenshtein Distances,D.S. Hirschberg
5. Parallel Computations of Levenshtein Distances,A. Apostolico and M.J. Atallah
6. Approximate String Searching,G.M. Landau and U. Vishkin
7. Dynamic Programming: Special Cases,R. Giancarlo
8. Shortest Common Superstrings,M. Li and T. Jiang
9. Two Dimensional Matching,A. Amir and M. Farach
10. Suffix Tree Data Structures for Matrices,R. Giancarlo and R. Grossi
11. Tree Pattern Matching,K. Zhang and D. Shasha

Anyone who has ever used an Internet search engine appreciates both the practical importance and the awesome power of pattern matching algorithms, which find a specific search string within a text file. Here, 11 chapters, which represent the combined work of 16 contributors, survey the state of the art. The focus of the chapters varies depending on whether authors treat serial or parallel al“A