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

 
Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 





Leave a Reply

Notify of
avatar
wpDiscuz