This is the second and final half of our two-part series on pattern matching, or string searching algorithms. In the first part, we covered the Knuth-Morris-Pratt (KMP) algorithm and in this segment, we’re going to present a new algorithm that originates from Boyer-Moore. It is currently considered the most efficient and practical algorithm, serving as a benchmark standard.
More Pattern Matching Algorithms: B-M - Final Words (Page 4 of 4 )
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.
ÞBoyer-Moore Algorithm (implementation, description, visualization), Institut d'électronique et d'informatique Gaspard-Monge, C. CHARRAS and T. LECROQ.
DISCLAIMER: The content provided in this article is not warranted or guaranteed by Developer Shed, Inc. The content provided is intended for entertainment and/or educational purposes in order to introduce to the reader key ideas, concepts, and/or product reviews. As such it is incumbent upon the reader to employ real-world tactics for security and implementation of best practices. We are not liable for any negative consequences that may result from implementing any information covered in our articles or tutorials. If this is a hardware review, it is not recommended to open and/or modify your hardware.