to construct the failure functionwe use the method shown in code fragment which is "bootstrappingprocess quite similar to the kmpmatch algorithm we compare the pattern to itself as in the kmp algorithm each time we have two characters that matchwe set (ij note that since we have throughout the execution of the algorithmf( is always defined when we need to use it code fragment computation of the failure function used in the kmp pattern matching algorithm note how the algorithm uses the previous values of the failure function to efficiently compute new values algorithm kmpfailurefunction runs in (mtime its analysis is analogous to that of algorithm kmpmatch thuswe haveproposition the knuth-morris-pratt algorithm performs pattern matching on text string of length and pattern string of length in ( mtime