About the Book
A string is just a sequence of letters.
But strings can be massive. Plant and animal genomes are strings billions
of letters long on the simple alphabet Internet traffic among billions
of websites is a collection of strings that amount to quadrillions of computer
bits every day.
Such strings are regularly searched,
probably millions of times a day, for patterns of all kinds - genomic codes
for genes and chromosomes, indicators of terrorist activity, and many others.
The search for patterns is fundamental to many fields molecular biology,
cryptography, data compression, computer vision, speech recognition, computational
geometry.
This book provides a basic general
introduction to the algorithms (methods) that efficiently compute patterns
in strings. It focuses on results that can be explained with reasonable
economy and simplicity, but its 250 references also enable the reader to
access current state-of-the-art methodology.
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.
Related
Books
Algorithms/Advanced Data
Structures - Programming Courses (Algorithms/Advanced
Data Structures)
Table of 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 |
