Hands-On Data Structures and Algorithms with Python - Second Edition

Understanding KMP algorithms

The KMP pattern matching algorithm uses a pattern that has overlap in the pattern itself so that it avoids unnecessary comparisons. The main idea behind the KMP algorithm is to detect how much the pattern should be shifted, based on the overlaps in the patterns. The algorithm works as follows:

1. First, we precompute the prefix function for the given pattern and initialize a counter, q, that represents the number of characters that matched.
2. We start by comparing the first character of the pattern with the first character of the text string, and if this matches, then we increment the counter, q, for the pattern and the counter for the text string, and we compare the next character.
3. If there is a mismatch, then we ...