Preface

The design of algorithms that process strings and texts goes back at least twenty five years. In particular, the last ten of those years have produced an explosion of new results. This progress is due in part to the human genome effort, to which string algorithms can make an important contribution.

While text algorithms can be viewed as part of the general field of algorithmic research, it has developed into a respectable subfield on its own. This subfield nicely combines theory and practice. The theory deals with symmetries and periodicities in strings, which in practice may lead to the development of fast new algorithms.

One measure of the vibrance of this new subfield is the ongoing success of a conference devoted to its study. The Conference on Combinatorial Pattern Matching will be holding its fifth meeting in the summer of 1994 to present theoretical results, new algorithms, and new applications of these algorithms.

Following the remarkable progress in this new field, Maxime Crochemore and Wojciech Rytter embarked on the right project at the right time— writing a textbook on text algorithms. Both authors have made important contributions to the field and therefore are excellent choices for the job.

About ten years ago, in a workshop that preceded the conference (called Combinatorial Algorithms on Words) I gave a lecture entitled “Open Problems in Stringology” [Ga 85a]. (Stringology has become the nickname of this new subfield.) In that lecture I described one dozen open problems. It gives me great pleasure to report that about half of these problems have either been solved or significant progress has been made towards their complete solution. Some of these new developments appear in Crochemore and Rytter’s new book. The recent Handbook of Theoretical Computer Science includes an excellent chapter entitled “Algorithms for finding patterns in strings” by A.V. Aho, one of the earliest contributors to text algorithms. Each time I have met Aho in the last fifteen years he has encouraged me to try and find a better algorithm for the membership problem for regular expressions, one of my twelve open problems. An improved solution to this problem would have significant practical consequences; in particular, it would improve the performance of the popular EGREP^{TM} program used by Unix^{TM}. See chapter 7 of Crochemore and Rytter’s book for more details.

Since the research on text algorithms continues, it is not possible to have a book that completely covers the area. Looking at the table of contents of this book, I am convinced that its fifteen chapters cover nicely many of the major developments in the field. Crochemore and Rytter have succeeded in producing a textbook that is as thorough as it is timely.

Zvi Galil

Acknowledgements

We have worked on this book during visits to each other at LIPN (University of Paris-Nord), Instytut Informatyk (University of Warsaw), LITP (University Paris 7), and Institut Gaspard Monge (University of Marne la Vallée). We warmly thank our colleagues of all these laboratories for the kind and stimulating atmosphere that has favoured the creation of the book. We especially thank the persons that help us produce that text by reading preliminary versions of some chapters, or by their comments: Véronique Bruyère, Richard Cole, Artur Czumaj, Zvi Galil, Leszek Ga̧sieniec, Christophe Hancart, Thierry Lecroq, Larry Larmore, Dominique Perrin, Giuseppina Rindone, Marc Zipstein.

Maxime Crochemore, Wojciech Rytter