Knuth Morris Pratt Algorithm in Python

Introduction:

In this tutorial, we are learning about the Knuth Morris Pratt algorithm in Python. The Knuth Morris Pratt algorithm is also known as KMP. When we create an LPS sequence for a sequence pattern, KMP will be similar to a simple pattern search. The only difference is that KMP uses LPS to continue from the same position where the conflict occurred, rather than going forward one character in the text and starting from the beginning of the string pattern. Now, here we are given the text txt[0..n-1] and the pattern pat[0..m-1], then write the function search(char pat[], char txt[]) to print all occurrences of pat[] in txt []. You can assume that n > m.

Example:

Now, we give some examples of input and its corresponding output for Knuth Morris Pratt or KMP algorithm in Python. The examples are given below -

Program Code:

Pattern searching is an important topic in computer science. When we search for strings in Notepad or Word file or in a browser or database, then a standard search algorithm is used to display the search results. So, now we give an example of Knuth Morris Pratt or KMP algorithm in Python. The code is given below -

Output:

Now, we compile the above code in Python, and after successful compilation, we run it. The output is given below -

 The pattern is found at index: 0 The pattern is found at index: 9 The pattern is found at index: 12 The pattern is found at index: 28 The pattern is found at index: 6 

The disadvantage of the naive string matching algorithm is that the algorithm runs very slowly. This means that the time complexity of the algorithm is very high. To solve this problem, we can use the KMP string matching algorithm emerged. It improves the time complexity of string matching algorithms to O(n), linear time.