Understanding the prefix-function of the Knuth-Morris-Pratt algorithm

Intuition is nothing but the outcome of earlier intellectual experience.    – Albert Einstein

There are plenty of tutorials about the ideas of the KMP algorithm, leaving us the wonder and owe of its magnificent simplicity and effectiveness. But one important part is frequently missing – why the prefix function can be computed in that particular way; what is the rationale behind the computation of the prefix function. This post aims to demystify the prefix function and elaborate on the proofs to understand why it works.

Let’s first review the computation of the prefix function, as shown below.
Screen Shot 2016-04-20 at 5.37.41 PM Continue reading “Understanding the prefix-function of the Knuth-Morris-Pratt algorithm”