More Pattern Matching Algorithms: B-M

We’ve come to the end of this article. Throughout this tutorial we have presented the Boyer-Moore pattern matching algorithm. It is one of the best and is currently considered a standard for benchmarking string searching applications. It is one of those underlying concepts that is widely implemented in our everyday lives, starting from find functions in word processors up to PHP applications, such as in Wikipedia.

As always, we can’t leave the creation of an application without presenting some real-world proof that can serve as an example of its execution. Check out the attached screenshot below. The source string is: assdbwfaswasdfbbsswasdfbwasdfbbs. The pattern is: asdfbbs. There are two matches: on positions 10 and 15. Enjoy!

Here is your chance to download the entire source code of this algorithm, if you had problems trying to implement and make use of the presented code snippets. Feel free to download and play around with it.

Now I’d like to invite you to join our ever-growing and friendly community at Dev Hardware Forums. We are specializing in computer hardware, software, and consumer electronics. Also, don’t forget to check out the communities at our sister sites. Whatever problems you may face, we’ll do our best to help.

As a final note, please glance over to the following list of references. All of the following authors have contributed much to computer science. I’m wholeheartedly advocating their work as a valid source of reference.

References:

Þ       BOYER R.S., MOORE J.S., 1977, A fast string searching algorithm.

Þ       CHRISTIAN CHARRAS, THIERRY LECROQ, Handbook of Exact String-Matching Algorithms

Þ       R. NIGEL HORSPOOL, 1980, Practical Fast Searching in Strings.

Þ       Boyer-Moore Algorithm (implementation, description, visualization), Institut d'électronique et d'informatique Gaspard-Monge, C. CHARRAS and T. LECROQ.