# Implementation of KMP Algorithm – C, C++, Java, and Python 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

Output:

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

## C++

Output:

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

## Java

Output:

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

## Python

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? 