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