Jewels of Stringology

World Scientific Press, 2002
Maxime.Crochemore@univ-mlv.fr
University of Marne-la-Vallée, January 2002
M. Crochemore and W. Rytter, Jewels of Stringology, World Scientific, 2002, 310 pages. ISBN 981-02-4782-6.
cover

Presentation

The term stringology is a popular nickname for string algorithms as well as for text algorithms. Usually text and string have the same meaning, more formally: a text is a sequence of symbols. Text or string is certainly the basic types to carry information. This book is a collection of the most beautiful and at the same time very classical algorithms on strings. The selection has been done by the authors, and is rather personal, among so many famous algorithms that were natural candidates to be included and that belong to a field that has become now rather popular.

One can partition algorithmic problems discussed in this book into practical and theoretical problems. Certainly string matching and data compression are in the first class, while most problems related to symmetries and repetitions are in the second. However, we believe that all the problems are interesting from an algorithmic point of view and enable the reader to appreciate the importance of combinatorics on words.

In most textbooks on algorithms and data structures the presentation of efficient algorithms on words is quite short as compared to issues in graph theory, sorting, searching, and some other areas. At the same time, there are many presentations of interesting algorithms on words accessible only in journals and in a form directed mainly at specialists. There are still not many books on text algorithms, especially the books which are oriented towards undergraduate and graduate students. We hope that this book will cover a gap on algorithms on words in book literature, and bring together the many results presently dispersed in the masses of journal articles.

Table of contents

  1. Stringology
  2. Basic String Searching Algorithms
  3. Preprocessing for Basic Searchings
  4. On-Line Construction of Suffix Trees
  5. More on Suffix Trees
  6. Subword Graphs
  7. Text Algorithms Related to Sorting
  8. Symmetries and Repetitions in Texts
  9. Constant-Space Searchings
  10. Text Compression Techniques
  11. Automata-Theoretic Approach
  12. Approximate Pattern Matching
  13. Matching by Dueling and Sampling
  14. Two-Dimensional Pattern Matching
  15. Two-Dimensional Periodicities
  16. Parallel Text Algorithms
  17. Miscellaneous

Other kind of stringology


Bibliography

A. Apostolico and Z. Galil, editors, Pattern Matching Algorithms, Oxford University Press, New York, 1997, 377 pages.
M. Crochemore, C. Hancart et T. Lecroq, Algorithmique du texte, Vuibert, Paris, 2001, 347 pages.
M. Crochemore and W. Rytter, Text Algorithms, Oxford University Press, New York, 1994, 412 pages.
D. Gusfield, Algorithms on Strings, Trees, and Sequences, Cambridge University Press, New York, 1997, 534 pages.
W. F. Smyth, Computing Patterns in Strings, Addison-Wesley, 2002.
G.A. Stephen, String Searching Algorithms, World Scientific Publishing Co., 1994, 243 pages.
Institut Gaspard-Monge, Laboratoire d'informatique, 3 January 2002, Maxime Crochemore