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

The prefix function

The prefix function (also known as the failure function) finds the pattern in the pattern itself. It tries to find how much the previous comparisons can be reused due to repetition in the pattern itself when there is a mismatch. It has a value that is mainly the longest prefix, which is also a suffix.

For example, if we have a prefix function for a pattern where all of the characters are different, the prefix function would have a value of 0, meaning that if we find any mismatch, the pattern would be shifted by the number of characters in the pattern. It also means that there is no overlap in the pattern, and no previous comparisons would be reused. We start by comparing from the first character of the pattern with the ...