Home arrow Development Cycles arrow Page 4 - More Pattern Matching Algorithms: B-M
DEVELOPMENT CYCLES

More Pattern Matching Algorithms: B-M


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, were 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.

Author Info:
By: Barzan "Tony" Antal
Rating: 4 stars4 stars4 stars4 stars4 stars / 7
August 05, 2008
TABLE OF CONTENTS:
  1. · More Pattern Matching Algorithms: B-M
  2. · The Theory
  3. · Implementation
  4. · Final Words

print this article
SEARCH DEVARTICLES

More Pattern Matching Algorithms: B-M - Final Words
(Page 4 of 4 )

Weve 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 cant 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 Id 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, dont forget to check out the communities at our sister sites. Whatever problems you may face, well 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. Im 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.


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.

blog comments powered by Disqus
DEVELOPMENT CYCLES ARTICLES

- Division of Large Numbers
- Branch and Bound Algorithm Technique
- Dynamic Programming Algorithm Technique
- Genetic Algorithm Techniques
- Greedy Strategy as an Algorithm Technique
- Divide and Conquer Algorithm Technique
- The Backtracking Algorithm Technique
- More Pattern Matching Algorithms: B-M
- Pattern Matching Algorithms Demystified: KMP
- Coding Standards
- A Peek into the Future: Transactional Memory
- Learning About the Graph Construct using Gam...
- Learning About the Graph Construct using Gam...
- Learning About the Graph Construct using Gam...
- How to Strike a Match

Watch our Tech Videos 
Dev Articles Forums 
 RSS  Articles
 RSS  Forums
 RSS  All Feeds
Write For Us 
Weekly Newsletter
 
Developer Updates  
Free Website Content 
Contact Us 
Site Map 
Privacy Policy 
Support 

Developer Shed Affiliates

 




© 2003-2017 by Developer Shed. All rights reserved. DS Cluster - Follow our Sitemap
Popular Web Development Topics
All Web Development Tutorials