The Knuthmorrispratt Algorithm
The KnuthMorrisPratt algorithm: We now present a lineartime stringmatching algorithm due to Knuth, Morris, and Pratt. Their algorithm avoids the computation of the transition function δ altogether, and its matching time is Θ(n) using just an auxiliary function π[1 ‥ m] precomputed from the pattern in time Θ(m). The array π allows the transition function δ to be computed efficiently (in an amortized sense) "on the fly" as needed. Roughly speaking, for any state q = 0, 1, . . . , m and any character a ∈ Σ, the value π[q] contains the information that is independent of a and is needed to compute δ(q, a). (This remark will be clarified shortly.) Since the array π has only m entries, whereas δ has Θ(m Σ) entries, we save a factor of Σ in the preprocessing time by computing π rather than δ.
The prefix function for a pattern: The prefix function π for a pattern encapsulates knowledge about how the pattern matches against shifts of itself. This information can be used to avoid testing useless shifts in the naive patternmatching algorithm or to avoid the precomputation of δ for a stringmatching automaton.
Consider the operation of the naive string matcher. Figure 32.10(a) shows a particular shift s of a template containing the pattern P = ababaca against a text T. For this example, q = 5 of the characters have matched successfully, but the 6th pattern character fails to match the corresponding text character. The information that q characters have matched successfully determines the corresponding text characters. Knowing these q text characters allows us to determine immediately that certain shifts are invalid. In the example of the figure, the shift s 1 is necessarily invalid, since the first pattern character (a) would be aligned with a text character that is known to match with the second pattern character (b). The shift s′ = s 2 shown in part (b) of the figure, however, aligns the first three pattern characters with three text characters that must necessarily match. In general, it is useful to know the answer to the following question:

Given that pattern characters P[1 ‥ q] match text characters T[s 1 ‥ s q], what is the least shift s′ > s such that

Such a shift s′ is the first shift greater than s that is not necessarily invalid due to our knowledge of T[s 1 ‥ s q]. In the best case, we have that s′ = s q, and shifts s 1, s 2, . . . , s q  1 are all immediately ruled out. In any case, at the new shift s′ we don't need to compare the first k characters of P with the corresponding characters of T, since we are guaranteed that they match by equation (32.5).
The necessary information can be precomputed by comparing the pattern against itself, as illustrated in Figure 32.10(c). Since T[s′ 1 ‥ s′ k] is part of the known portion of the text, it is a suffix of the string P_{q}. Equation (32.5) can therefore be interpreted as asking for the largest k < q such that P_{k} ⊐ P_{q}. Then, s′ = s (q  k) is the next potentially valid shift. It turns out to be convenient to store the number k of matching characters at the new shift s′, rather than storing, say, s′  s. This information can be used to speed up both the naive stringmatching algorithm and the finiteautomaton matcher.
We formalize the precomputation required as follows. Given a pattern P[1 ‥ m], the prefix function for the pattern P is the function π : {1, 2, . . . , m} → {0, 1, . . . , m  1} such that
π[q] = max {k : k < q and P_{k} ⊐ P_{q}}.
That is, π[q] is the length of the longest prefix of P that is a proper suffix of P_{q}. As another example, Figure 32.11(a) gives the complete prefix function π for the pattern ababababca.