PCPlus 260: String searching

I write a monthly column for PCPlus, a computer news-views-n-reviews magazine in the UK (actually there are 13 issues a year — there's an Xmas issue as well — so it's a bit more than monthly). The column is called Theory Workshop and appears in the back of every issue. When I signed up, my editor and the magazine were gracious enough to allow me to reprint the articles here after say a year or so. After all, the PDFs do appear on each issue's DVD after a couple of months.

The sixth article I wrote for PCPlus was on the Boyer-Moore string searching algorithm. This one was fairly easy to write and as before I was getting into Adobe Illustrator and producing some more compelling images. Boyer-Moore has always fascinated me — even though it didn't appear in the book — because it can be so much faster than brute-force searching. The Knuth-Pratt algorithm on the other hand, another "faster" search algorithm, is almost never used or referenced as far as I can gather, mainly because of its computational overhead and difficulty of implementation. Mind you, Boyer-Moore isn't particularly easy to implement either, and so I didn't attempt to show any code whatsoever in the article.

looking at the PDF versus what I wrote in the Word doc I sent up, I see that I was starting to get better at choosing titles and straps and so on so that they would fit and would follow the theme of that part of the magazine.

This article first appeared in issue 260, October 2007.

You can download the PDF here.

  Loading links to posts on similar topics...