Algorithms on Strings

I was first exposed to string matching by given to read “Algorithms for Finding Patterns in Strings” back in 1990, when I naively asked Prof. Stathis Zachos something like “How does grep work?”.

Time passed, I became a system administrator and most of my exposure to string matching was through scripts and sysadmin stuff automation. Automata are nice, but Perl and shell brought food to the table.

These memories surfaced because I got to read “Algorithms on Strings” in January thanks to Bill Gasarch. Complete, self-contained and with plain and well understood English, the book covers the subject fulfilling simultaneously the needs of those who want to just read the theory, those who want to see the proofs and those who just want to write code.

The pseudocode in the book is understood by anyone who has ever written a single program in C or Java. It either introduces new functions or makes use of others previously defined. This may make it a little difficult at first for people who need to write something described in, for example, chapter six and may find themselves reading from chapter one up to six. In this process the book manages to educate even the programmer who does not care about theory not only about how to do certain functions, but why they are done the way they are. As a plus, references to appropriate Unix shell tools (e.g. diff) are given when appropriate.

A really impressive book, definitely worth your time! A book that you can use both to learn about stuff and as a reference.

4 thoughts on “Algorithms on Strings

  1. Thiery Lecroq in the list of authors made me:
    a. Certain that this is a great book
    b. Wonder how does it compare to the “Handbook of exact string matching algorithms”
    c. Reach for the credit card in my wallet ;-)

    Any insight on (b) would be appreciated, I have a hunch you’ve read both ;)

    1. “Handbook of exact string matching algorithms” has C code, not pseudocode. Both books use the same notation and the figures are constructed in a similar way. It beats exact string matching to death, which should be enough for most. Plus it is available as PDF.

      I consider myself lucky that the book was sent to me for review thanks to Bill Gasarch, for I do not know whether I would have bought it without browsing it at a local library first.

      Last year I had tried to buy “String Algorithmics” (also by Lecroq) but although the publisher mailed it to me twice, it never reached me :(

      Keep in mind that “String Algorithmics” and “Handbook” were published in 2004 and “Algorithms on Strings” in 2007.

      I would buy it for completeness and because I am a string junkie.

  2. I think this post was right on time. I’m preparing to do one of my usual deposits to amazon, so .. it will be a bit bigger than I previously thought ;)

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s