Implementation of KMP Algorithm – C, C++, Java, and Python

Google Translate Icon

This post will implement the KMP algorithm in C, C++, Java, and Python programming language.

We have seen that the naive algorithm for pattern matching runs in O(n.m) 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 a different pattern character over and over again.

 
The KMP Algorithm (or Knuth, Morris, and Pratt string searching algorithm) cleverly uses the previous comparison data. It can search for 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 a partial match table takes O(m) time. Therefore, the overall time complexity of the KMP algorithm is O(m + n).

 
Please refer to the following link for a detailed explanation of the KMP algorithm, one of the best explanations available on the web:

The Knuth–Morris–Pratt Algorithm in my own words

Practice this algorithm

 
The algorithm can be implemented as follows in C, C++, Java, and Python:

C


Download  Run Code

Output:

The pattern occurs with shift 2
The pattern occurs with shift 8

C++


Download  Run Code

Output:

The pattern occurs with shift 2
The pattern occurs with shift 8

Java


Download  Run Code

Output:

The pattern occurs with shift 2
The pattern occurs with shift 8

Python


Download  Run Code

Output:

The pattern occurs with shift 2
The pattern occurs with shift 8

Rate this post

Average rating 4.44/5. Vote count: 158

No votes so far! Be the first to rate this post.

We are sorry that this post was not useful for you!

Tell us how we can improve this post?




Thanks for reading.

Please use our online compiler to post code in comments using C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.

Like us? Refer us to your friends and help us grow. Happy coding :)



Subscribe
Notify of
guest
6 Comments
Most Voted
Newest Oldest
Inline Feedbacks
View all comments
Do NOT follow this link or you will be banned from the site!