This is the fourth 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 will learn more about the pattern preprocessing phase of the KMP algorithm. You will learn how to create a partial match table for a given string by inspection. In doing so, you will learn that pattern preprocessing captures and stores information about the way sequences of characters are repeated within each possible partial match for a string. You will also learn how this information is accessed during a KMP search in the event of a partial match. This lesson introduces some established terminology including proper prefix, suffix and lps value. You will meet this terminology again when you learn to implement a KMP search.
Before continuing, make sure you are familiar with the KMP algorithm, as covered in the previous lesson
Chapters:
00:00 Introduction
00:52 Create a partial match table example 1
03:52 Create a partial match table example 2
04:32 Established terminology
07:39 Accessing the partial match table