Jewels of Stringology

Jewels of Stringology: Text Algorithms is a book on algorithms for pattern matching in strings and related problems. It was written by Maxime Crochemore and Wojciech Rytter, and published by World Scientific in 2003.

Topics

The first topics of the book are two basic string-searching algorithms for finding exactly-matching substrings, the Knuth–Morris–Pratt algorithm and the Boyer–Moore string-search algorithm. It then describes the suffix tree, an index for quickly looking up matching substrings, and two algorithms for constructing it. Other topics in the book include the construction of deterministic finite automata for pattern recognition, the discovery of repeated patterns in strings, constant-space string matching algorithms, and the lossless compression of strings. Approximate string matching is covered in several variations including edit distance and the longest common subsequence problem. The book concludes with advanced topics including two-dimensional pattern matching, parallel algorithms for pattern matching, the shortest common superstring problem, parameterized pattern matching and duplicate code detection, and the Rabin–Karp algorithm.

Audience and reception

The book is written for an audience familiar with algorithm design and analysis, but not necessarily familiar with string algorithms. Reviewer Rolf Klein suggests that this target audience may be narrow, as he evaluates the book as being too difficult for many students, but not supplying as much depth for experts as the same authors' earlier book Text Algorithms (1994).

Reviewer Shoshana Marcus writes that the algorithms chosen for inclusion in the book are "elegant yet fundamental" but have often been overlooked by more general algorithms textbooks. She writes that the book itself should become a valuable reference for researchers in this area, and that it could also be used to supplement undergraduate or graduate course material in algorithms. Reviewer Ricardo Baeza-Yates suggests that the book's omission of bit-level parallel programming techniques reflects its bias towards theoretical rather than practical methods, but nevertheless agrees with its suitability for graduate courses.