Algorithms on Strings

by Maxime Crochemore

This text and reference on string processes and pattern matching presents examples related to the automatic processing of natural language, to the analysis of molecular sequences and to the management of textual databases. Algorithms are described in a C-like language, with correctness proofs and complexity analysis, to make them ready to implement. The book will be an important resource for students and researchers in theoretical computer science, computational linguistics, computational biology, and software engineering.

Genres: Algorithms, Computer Science, Software

392 pages, Hardcover

First published January 1, 2001

Reviews

[Ushan · Rating 4 out of 5]

Different variants of the Boyer-Moore algorithm, suffix arrays, suffix trees, and the like. It never crossed my mind before that if you do binary search in an array, and arrive at an element, there is a unique sequence of low bounds and high bounds that got you there; using this fact, it is possible to preprocess a sorted array of strings so that searching for an element in it will be asymptotically faster than simple binary search.

[Nick Black · Rating 5 out of 5]

This is the new best book on string algorithms, replacing Navarro's Flexible Pattern Matching in Strings at the top. Actually, picking Navarro up, spinning him around a few times, and hurling him into a pit through which he falls for five-thousand years (and I *really* liked Navarro's book -- it totally set my efforts at the job (then Reflex Security, where I was building the Reflex Interceptor IPS) in a new direction back in 2003). One of the best computer science textbooks I've ever seen. If you do string algorithms, this ought be the first book on your shelf.
------
Amazon 2008-12-30. I bit the bullet and grabbed a new copy -- I didn't want 2008 to close without securing what promises to be a rare and exquisite treat. Maxime Crochemore (link de-Gaullized for your pleasure) is certifiably: da man, and a delighted stringalg community has been waiting for this with breath bated.

(was: YAY! Crochemore published in 2006 my favorite text on combinatorial matching, Jewels of Stringology (with Wojciech Rytter). Between Crochemore, Rytter and Navarro, Old Europe and South America are pulling ahead in the combinatorial automata racket...I intend to change all that, though =) (malicious grin). Anyway, this is sure to be an epic treatment of my all-time most beloved area of algorithms, with likely applications to my day-to-day work both in the laboratory and at the office.)

[Tim Dumol · Rating 5 out of 5]

Formal and rigorous look at string algorithms.