Implementation of KMP Algorithm in C, C++ and Java

In this post, we will implement KMP Algorithm in C, C++ and Java programming language.


 

We have seen that the Naive Algorithm for pattern matching runs in O(nm) time where n is the length of the text and m is the length of the pattern. This is because the algorithm doesn’t remember any information about the past matched characters. It basically matches a character with different pattern character over and over again.

 
The KMP Algorithm (or Knuth, Morris and Pratt string searching algorithm) cleverly make use of previous comparison’s data. It can search a pattern in O(n) time as it never re-compares a text symbol that has matched a pattern symbol. However, it uses a partial match table to analyze the pattern structure. Construction of partial match table takes O(m) time. Therefore, the overall complexity of the KMP algorithm is O(m + n).

 
Please refer below link for detailed explanation of KMP algorithm, one of the best explanation available on web.

 
The Knuth-Morris-Pratt Algorithm in my own words

 

C

Download   Run Code

Output:

Pattern occurs with shift 2
Pattern occurs with shift 8

C++

Download   Run Code

Output:

Pattern occurs with shift 2
Pattern occurs with shift 8

Java

Download   Run Code

Output:

Pattern occurs with shift 2
Pattern occurs with shift 8

 
1 Star2 Stars3 Stars4 Stars5 Stars (3 votes, average: 4.33 out of 5)

Loading...

Thanks for reading.

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂
 


Leave a Reply

avatar
  Subscribe  
Notify of