Analytic Pattern Matching

The book discusses questions such as how to find a given subword in a long string over a finite alphabet, or how to count the number of occurrences of a subword over that alphabet. These questions often appear in information theory, statistical physics and molecular biology; but this is a mathematics book, and a difficult one at that.

The book has two parts. The first one contains results from analytic combinatorics about the families of problems described above, and the second one covers the application of these results to various data structures on words over finite alphabets, such as various kinds of trees, (tries and digital search trees). The Lempel-Ziv'78 compression algorithm is also discussed.

The book is dedicated to the memory of Philippe Flajolet and has a foreword by Robert Sedgewick. Indeed, many, or maybe even most, readers of this book will be researchers and very advanced graduate students who have read Analytic Combinatorics by Flajolet and Sedgewick. This book will be even more challenging, however, in that it is more specialized, starts from a much higher level, and does not provide quite as much context as the mentioned volume.

Each chapter ends with a list of 15 to 20 exercises, but they do not have their solutions, or even, hints, in the book. On the other hand, the bibliographical notes at the end of each chapter are detailed and useful.

Miklós Bóna is Professor of Mathematics at the University of Florida.