The Knuth-Morris-Pratt algorithm

Knuth, Morris, and Pratt developed a linear-time string matching algorithm that avoids computing the transition function $\delta $ altogether. Instead, the KMP algorithm uses an auxiliary function , which it precomputes from the pattern in \(\Theta(m)\) time and stores in an array \(\pi[1:m]\). The array \(\pi\) allows the algorithm to compute the transition function \(\delta\) efficently (in an amortized sense) "on the fly" as needed. Loosely speaking, for any state \(q = 0,1,...,m\) and any character $a \in \sum $, the value \(\pi [q]\) contains the information needed to compute .