This is the sixth in a series of computer science lessons about string matching algorithms and how to implement them. String matching is not just about text processing, it has applications in the fields of artificial intelligence, cybersecurity and computational biology, to name but a few. String matching algorithms include the naive algorithm, KMP, Boyer Moore and Rabin Karp.

Some of these are particularly suited to specialist applications like DNA sequencing, data mining and network intrusion detection systems.

In this lesson you’ll learn how to write a program to implement a complete KMP search. A pseudocode version of program is visualised with an example first, and then demonstrated in VB.NET, C# and Python.

In the previous lessons you learned how the KMP algorithm works, and why it is so much better than the naïve, brut force, approach. You also learned how to implement the pattern preprocessing phase of the KMP algorithm. You’re advised to familiarise yourself with the content of the previous lessons before continuing. It is also assumed that you already have some programming experience.

Chapters:
00:00 Introduction
00:48 Example Input string and pattern
00:56 Pseudocode step through and visualisation
05:48 VB.NET code for a KMP search
06:58 C# code for a KMP search
07:28 Python code for a KMP search