Computing Patterns in Strings

Description
The computation of patterns in strings is a fundamental requirement in many areas of science and information processing.  The operation of a text editor, the lexical analysis of a computer program, the functioning of a finite automaton, the retrieval of information from a database - these are all activities which may require that patterns be located and computed.   In other areas of science, the algorithms that compute patterns have applications in such diverse fields as data compression, cryptography, speech recognition, computer vision, computational geometry and molecular biology.

Contents
Preface
PART I  STRINGS AND ALGORITHMS
1. Properties of Strings
2. Patterns?  What Patterns?
3. Strings, Famous and Infamous
4. Good Algorithms and Good Test Data
PART II  COMPUTING INTRINSIC PATTERNS
5. Trees Derived from Strings
6. Decomposing a String
PART III  COMPUTING SPECIFIC PATTERNS 7. Basic Algorithms
8. Son of BM Rides Again!
9. String Distance Algorithms
10. Approximate Pattern-Matching
11. Regular Expressions and Multiple Patterns
PART IV  COMPUTING GENERIC PATTERNS
12. Repetitions (Periodicity)
13. Extensions of Periodicity

Features

• Step-by-step approach - enables students to gradually build up their understanding of the topics.
• Many illustrative examples - apply a real life element so students understand how what they are learning is applied in the 'real world'.
• Over 500 exercises to clarify/extend ideas explained in the text - provide students with the opportunity to test their understanding.
• Contains summaries and discussions of current research and applications - an ideal revision tool for students to further help clarify the concepts.
  

Author
Bill Smyth is currently teaching at McMaster University, Canada