Home arrow Development Cycles arrow Pattern Matching Algorithms Demystified: KMP

Pattern Matching Algorithms Demystified: KMP

Chances are that if you've worked with strings then you have also tried to locate a specific substring in the entire source string. In computer science this is called pattern matching or string matching. And to accomplish this task, there are a few classic algorithms. In this two-part series were going to discuss string searching algorithms. We will start with Knuth-Morris-Pratt.

Author Info:
By: Barzan "Tony" Antal
Rating: 4 stars4 stars4 stars4 stars4 stars / 19
July 29, 2008
  1. · Pattern Matching Algorithms Demystified: KMP
  2. · The Theory
  3. · C Implementation
  4. · Taking a Break

print this article

Pattern Matching Algorithms Demystified: KMP
(Page 1 of 4 )

Before we begin, Id like to point out that both of these articles are going to follow this scheme: first we will discuss the theory behind the algorithm. We need to grasp its concepts and methodology well enough that we should be able to run the algorithm on a few sample strings on a piece of paper. After this, we can move on to implementing and writing the code that does K-M-P. Ive opted for the C++ language.

Knuth-Morris-Pratt (abbreviated as KMP or K-M-P) is an algorithm discovered by Donald Knuth and Vaughan Pratt. Interestingly, J. H. Morris also figured out this exact algorithm. Later on, the three of them published it jointly. It is one of the classic algorithms that is always taught in algorithm analysis courses during string-related chapters. Its complexity O(m) in preprocessing and O(n) in search phase. Thus, the total time it takes can be shown as O(m+n), since it is composed of 2 phases.

The upcoming segment of this two-part series is going to cover the so-called Boyer-Moore (B-M) algorithm. It is a very effective, practical, and efficient algorithm. It is considered the standard benchmark for practical string search literature. Its preprocessing time is Θ(m + |Σ|) and its matching time is Ω(n/m), O(n). For a detailed overview on the asymptotic growth of functions and computational complexity theory, please check out this course from the Jack Baskin School of Engineering, UC Santa Cruz.

Now you know what to expect from this series. Ready, set, go!

blog comments powered by Disqus

- 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 

Developer Shed Affiliates


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